LOJ#2722 情报中心

╰+哭是因爲堅強的太久メ 2021-12-22 16:43 304阅读 0赞

![1332167-20190409200650468-2013514623.png][]

解：有个暴力是枚举两条链然后O（n）判定，可以得到15分。

还可以优化一下，枚举一条链，然后第二条链直接求两端点树上带权距离。可以做到O(m(n + m))，但是我用的树剖，跟上面那一档没啥区别Orz...

然后是链的部分，把所有链按照左端点小到大排序，左端点相同的时候按右端点小到大。

然后从右往左加。用一个树状数组维护前缀最大值。如果一个之前区间的左端点在我们当前区间的右端点内，就有交。

我们漏了一种情况：一个区间被另一个完全包含。于是新开一个树状数组维护即可。注意到这种情况在第一个树状数组中算出的答案不优，会被取代掉。

这样就有30分了。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

30分代码

接下来还有c = 0的部分分：枚举每条边，统计所有过它的链中权值最大的两条更新答案。拿线段树合并实现。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
      2 
      3 #define forson(x, i) for(int i = e[x]; i; i = edge[i].nex)
      4 
      5 typedef long long LL;
      6 const int N = 100010;
      7 const LL INF = 9e18;
      8 
      9 struct Edge {
     10     int nex, v;
     11     LL len;
     12 }edge[N << 1]; int tp;
     13 
     14 struct Node {
     15     int x, y;
     16     LL z, val;
     17     inline bool operator < (const Node &w) const {
     18         if(x != w.x) return x < w.x;
     19         return y < w.y;
     20     }
     21 }node[N];
     22 
     23 int n, e[N], m, fa[N], deep[N];
     24 int num, pos[N], son[N], siz[N], top[N];
     25 LL Sum[N], sum[N << 2], d[N], tag[N << 2];
     26 
     27 inline void add(int x, int y, LL z) {
     28     tp++;
     29     edge[tp].v = y;
     30     edge[tp].len = z;
     31     edge[tp].nex = e[x];
     32     e[x] = tp;
     33     return;
     34 }
     35 
     36 void DFS_1(int x, int f) { /// get fa son siz d deep
     37     fa[x] = f;
     38     deep[x] = deep[f] + 1;
     39     siz[x] = 1;
     40     forson(x, i) {
     41         int y = edge[i].v;
     42         if(y == f) continue;
     43         d[y] = d[x] + edge[i].len;
     44         DFS_1(y, x);
     45         siz[x] += siz[y];
     46         if(siz[y] > siz[son[x]]) {
     47             son[x] = y;
     48         }
     49     }
     50     return;
     51 }
     52 
     53 void DFS_2(int x, int f) { /// get top id pos
     54     pos[x] = ++num;
     55     top[x] = f;
     56     Sum[num] = d[x] - d[fa[x]];
     57     if(son[x]) {
     58         DFS_2(son[x], f);
     59     }
     60     forson(x, i) {
     61         int y = edge[i].v;
     62         if(y == fa[x] || y == son[x]) continue;
     63         DFS_2(y, y);
     64     }
     65     return;
     66 }
     67 
     68 inline int lca(int x, int y) {
     69     while(top[x] != top[y]) {
     70         if(deep[top[x]] > deep[top[y]]) {
     71             x = fa[top[x]];
     72         }
     73         else {
     74             y = fa[top[y]];
     75         }
     76     }
     77     return deep[x] < deep[y] ? x : y;
     78 }
     79 
     80 inline LL dis(int x, int y) {
     81     return d[x] + d[y] - 2 * d[lca(x, y)];
     82 }
     83 
     84 inline void pushdown(int l, int r, int o) {
     85     if(tag[o] != -1) {
     86         if(tag[o] == 0) {
     87             sum[o << 1] = sum[o << 1 | 1] = 0;
     88         }
     89         else {
     90             int mid = (l + r) >> 1;
     91             sum[o << 1] = Sum[mid] - Sum[l - 1];
     92             sum[o << 1 | 1] = Sum[r] - Sum[mid];
     93         }
     94         tag[o << 1] = tag[o << 1 | 1] = tag[o];
     95         tag[o] = -1;
     96     }
     97     return;
     98 }
     99 
    100 void Add(int L, int R, int l, int r, int o) {
    101     if(L <= l && r <= R) {
    102         sum[o] = Sum[r] - Sum[l - 1];
    103         tag[o] = 1;
    104         return;
    105     }
    106     int mid = (l + r) >> 1;
    107     pushdown(l, r, o);
    108     if(L <= mid) Add(L, R, l, mid, o << 1);
    109     if(mid < R) Add(L, R, mid + 1, r, o << 1 | 1);
    110     sum[o] = sum[o << 1] + sum[o << 1 | 1];
    111     return;
    112 }
    113 
    114 LL ask(int L, int R, int l, int r, int o) {
    115     if(L <= l && r <= R) {
    116         return sum[o];
    117     }
    118     int mid = (l + r) >> 1;
    119     pushdown(l, r, o);
    120     LL ans = 0;
    121     if(L <= mid) {
    122         ans += ask(L, R, l, mid, o << 1);
    123     }
    124     if(mid < R) {
    125         ans += ask(L, R, mid + 1, r, o << 1 | 1);
    126     }
    127     return ans;
    128 }
    129 
    130 inline void Add(int x, int y) {
    131     while(top[x] != top[y]) {
    132         if(deep[top[x]] > deep[top[y]]) {
    133             std::swap(x, y);
    134         }
    135         Add(pos[top[y]], pos[y], 1, n, 1);
    136         y = fa[top[y]];
    137     }
    138     if(deep[x] > deep[y]) std::swap(x, y);
    139     if(x != y) Add(pos[x] + 1, pos[y], 1, n, 1);
    140     return;
    141 }
    142 
    143 inline LL ask(int x, int y) {
    144     LL ans = 0;
    145     while(top[x] != top[y]) {
    146         if(deep[top[x]] > deep[top[y]]) {
    147             std::swap(x, y);
    148         }
    149         ans += ask(pos[top[y]], pos[y], 1, n, 1);
    150         y = fa[top[y]];
    151     }
    152     if(deep[x] > deep[y]) std::swap(x, y);
    153     if(x != y) ans += ask(pos[x] + 1, pos[y], 1, n, 1);
    154     return ans;
    155 }
    156 
    157 inline void clear() {
    158     memset(e + 1, 0, n * sizeof(int));
    159     memset(son + 1, 0, n * sizeof(int));
    160     tp = 0;
    161     num = 0;
    162     return;
    163 }
    164 /*
    165 1
    166 5
    167 1 2 1
    168 2 3 3
    169 3 4 3
    170 1 5 9
    171 2
    172 1 5 5
    173 2 3 8
    174 */
    175 
    176 namespace Line {
    177     LL ta[N], ta2[N];
    178     inline LL ask(int i) {
    179         LL ans = -INF;
    180         for(; i; i -= i & (-i)) {
    181             ans = std::max(ans, ta[i]);
    182         }
    183         return ans;
    184     }
    185     inline void Add(int i, LL v) {
    186         for(; i <= n; i += i & (-i)) {
    187             ta[i] = std::max(ta[i], v);
    188         }
    189         return;
    190     }
    191     inline LL ask2(int i) {
    192         LL ans = -INF;
    193         for(; i; i -= i & (-i)) {
    194             ans = std::max(ans, ta2[i]);
    195         }
    196         return ans;
    197     }
    198     inline void Add2(int i, LL v) {
    199         for(; i <= n; i += i & (-i)) {
    200             ta2[i] = std::max(ta2[i], v);
    201         }
    202         return;
    203     }
    204     inline void solve() {
    205         for(int i = 1; i <= n; i++) ta2[i] = ta[i] = -INF;
    206         LL ans = -INF;
    207         std::sort(node + 1, node + m + 1);
    208         for(int i = m; i >= 1; i--) {
    209             LL temp = ask(node[i].y - 1);
    210             if(temp != -INF) {
    211                 ans = std::max(ans, temp + node[i].val - Sum[node[i].y]);
    212             }
    213             temp = ask2(node[i].y);
    214             if(temp != -INF) {
    215                 ans = std::max(ans, temp + node[i].val);
    216             }
    217             Add(node[i].x, node[i].val + Sum[node[i].x]);
    218             Add2(node[i].y, node[i].val + Sum[node[i].x] - Sum[node[i].y]);
    219         }
    220         if(ans == -INF) puts("F");
    221         else {
    222             printf("%lld\n", ans);
    223         }
    224         return;
    225     }
    226 }
    227 
    228 namespace C0 {
    229     int rt[N], xx;
    230     LL Ans, X[N];
    231     std::vector<int> v[N];
    232     namespace seg {
    233         const int M = 20000010;
    234         int ls[M], rs[M], tot, cnt[M];
    235         LL sum[M];
    236         void insert(int p, int v, int l, int r, int &o) {
    237             if(!o) {
    238                 o = ++tot;
    239                 sum[o] = cnt[o] = ls[o] = rs[o] = 0;
    240             }
    241             if(l == r) {
    242                 sum[o] += v * X[r];
    243                 cnt[o] += v;
    244                 return;
    245             }
    246             int mid = (l + r) >> 1;
    247             if(p <= mid) {
    248                 insert(p, v, l, mid, ls[o]);
    249             }
    250             else {
    251                 insert(p, v, mid + 1, r, rs[o]);
    252             }
    253             sum[o] = sum[ls[o]] + sum[rs[o]];
    254             cnt[o] = cnt[ls[o]] + cnt[rs[o]];
    255             return;
    256         }
    257         LL ask(int k, int l, int r, int o) {
    258             if(l == r) {
    259                 return k * X[r];
    260             }
    261             int mid = (l + r) >> 1;
    262             if(k <= cnt[rs[o]]) {
    263                 return ask(k, mid + 1, r, rs[o]);
    264             }
    265             else {
    266                 return ask(k - cnt[rs[o]], l, mid, ls[o]) + sum[rs[o]];
    267             }
    268         }
    269         inline LL Ask(int x) {
    270             if(cnt[rt[x]] < 2) return -INF;
    271             return ask(2, 1, xx, rt[x]);
    272         }
    273         int merge(int x, int y) {
    274             if(!x || !y) return x | y;
    275             sum[x] += sum[y];
    276             cnt[x] += cnt[y];
    277             ls[x] = merge(ls[x], ls[y]);
    278             rs[x] = merge(rs[x], rs[y]);
    279             return x;
    280         }
    281         inline void Merge(int x, int y) {
    282             rt[x] = merge(rt[x], rt[y]);
    283             return;
    284         }
    285     }
    286     void DFS(int x, int f) {
    287         forson(x, i) {
    288             int y = edge[i].v;
    289             if(y == f) continue;
    290             DFS(y, x);
    291             Ans = std::max(Ans, seg::Ask(y));
    292             seg::Merge(x, y);
    293         }
    294         for(int i = 0; i < (int)v[x].size(); i++) {
    295             int t = v[x][i];
    296             if(t > 0) {
    297                 seg::insert(t, 1, 1, xx, rt[x]);
    298             }
    299             else {
    300                 seg::insert(-t, -1, 1, xx, rt[x]);
    301             }
    302         }
    303         return;
    304     }
    305     inline void solve() {
    306         memset(rt + 1, 0, n * sizeof(int));
    307         seg::tot = 0;
    308         Ans = -INF;
    309         for(int i = 1; i <= n; i++) v[i].clear();
    310         for(int i = 1; i <= m; i++) {
    311             X[i] = node[i].val;
    312         }
    313         std::sort(X + 1, X + m + 1);
    314         xx = std::unique(X + 1, X + m + 1) - X - 1;
    315         for(int i = 1; i <= m; i++) {
    316             int val = std::lower_bound(X + 1, X + xx + 1, node[i].val) - X;
    317             int x = node[i].x, y = node[i].y, z = lca(node[i].x, node[i].y);
    318             v[x].push_back(val);
    319             v[y].push_back(val);
    320             v[z].push_back(-val);
    321             v[z].push_back(-val);
    322         }
    323         DFS(1, 0);
    324         if(Ans == -INF) puts("F");
    325         else printf("%lld\n", Ans);
    326         return;
    327     }
    328 }
    329 
    330 /*
    331 50
    332 2
    333 1 2 914572059
    334 3
    335 1 2 213930211
    336 1 2 0
    337 2 2 0
    338 */
    339 inline void solve() {
    340 
    341     sum[1] = tag[1] = 0;
    342 
    343     scanf("%d", &n);
    344     LL z;
    345     bool FLAG = 1, c0 = 1;
    346     for(int i = 1, x, y; i < n; i++) {
    347         scanf("%d%d%lld", &x, &y, &z);
    348         add(x, y, z);
    349         add(y, x, z);
    350         if(z) c0 = 0;
    351         if(y != x + 1) {
    352             FLAG = 0;
    353         }
    354     }
    355 
    356     DFS_1(1, 0);
    357     DFS_2(1, 1);
    358 
    359     for(int i = 1; i <= n; i++) {
    360         Sum[i] += Sum[i - 1];
    361     }
    362 
    363     scanf("%d", &m);
    364     for(int i = 1; i <= m; i++) {
    365         scanf("%d%d%lld", &node[i].x, &node[i].y, &node[i].z);
    366         if(node[i].x > node[i].y) std::swap(node[i].x, node[i].y);
    367         else if(node[i].x == node[i].y) {
    368             m--;
    369             i--;
    370         }
    371         node[i].val = dis(node[i].x, node[i].y) - node[i].z;
    372         //printf("node %d [%d %d] val = %lld \n", i, node[i].x, node[i].y, node[i].val);
    373     }
    374     // solve
    375     if(FLAG) {
    376         Line::solve();
    377         clear();
    378         return;
    379     }
    380     if(c0) {
    381         C0::solve();
    382         clear();
    383         return;
    384     }
    385 
    386     if(m > 300) {
    387         clear();
    388         return;
    389     }
    390 
    391     LL ans = -INF;
    392     for(int i = 1; i < m; i++) {
    393         Add(node[i].x, node[i].y);
    394         for(int j = i + 1; j <= m; j++) {
    395             /// choose i j
    396             LL Val = ask(node[j].x, node[j].y);
    397             //printf("Val = %lld \n", Val);
    398             if(Val) {
    399                 ans = std::max(ans, node[i].val + node[j].val - Val);
    400             }
    401         }
    402         tag[1] = sum[1] = 0;
    403     }
    404     if(ans == -INF) {
    405         puts("F");
    406     }
    407     else {
    408         printf("%lld\n", ans);
    409     }
    410     clear();
    411     return;
    412 }
    413 
    414 int main() {
    415 
    416     int T;
    417     scanf("%d", &T);
    418     while(T--) solve();
    419     return 0;
    420 }

45分代码

接下来是这个东西...

![1332167-20190411164604840-2077384845.png][]

然而我只得到了20分...可能比较丑。

只枚举有公共部分的链：考虑枚举每条边，并m2枚举经过这条边的链。

这样两条链可能会在多条边上算多次，于是我们限定某一个链的lca是这条边的上端点。

具体一点，线段树合并搞出经过每条边的链，然后枚举以这条边为lca的链，预处理树上距离。然后枚举经过这条边的所有链，并更新答案。

其实可以O(1)lca和长链剖分O(1)k级祖先来优化，但是我已经写不动啦......

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /**
      2  * There is no end though there is a start in space. ---Infinity.
      3  * It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
      4  * Only the person who was wisdom can read the most foolish one from the history.
      5  * The fish that lives in the sea doesn't know the world in the land.
      6  * It also ruins and goes if they have wisdom.
      7  * It is funnier that man exceeds the speed of light than fish start living in the land.
      8  * It can be said that this is an final ultimatum from the god to the people who can fight.
      9  *
     10  * Steins;Gate
     11  */
     12 
     13 #include <bits/stdc++.h>
     14 
     15 #define forson(x, i) for(int i = e[x]; i; i = edge[i].nex)
     16 
     17 typedef long long LL;
     18 const int N = 100010, M = 20000010;
     19 const LL INF = 9e18;
     20 
     21 struct Edge {
     22     int nex, v;
     23     LL len;
     24     bool vis;
     25 }edge[N << 1]; int tp = 1;
     26 
     27 struct Node {
     28     int x, y;
     29     LL z, val;
     30     inline bool operator < (const Node &w) const {
     31         if(x != w.x) return x < w.x;
     32         return y < w.y;
     33     }
     34 }node[N];
     35 
     36 int n, e[N], m, fa[N], deep[N], ls[M], rs[M], tot;
     37 int num, pos[N], son[N], siz[N], top[N], rt[N], pw[N];
     38 LL Sum[N], sum[N << 2], d[N], tag[N << 2];
     39 
     40 inline void add(int x, int y, LL z) {
     41     tp++;
     42     edge[tp].v = y;
     43     edge[tp].len = z;
     44     edge[tp].vis = 0;
     45     edge[tp].nex = e[x];
     46     e[x] = tp;
     47     return;
     48 }
     49 
     50 void DFS_1(int x, int f) { /// get fa son siz d deep
     51     fa[x] = f;
     52     deep[x] = deep[f] + 1;
     53     siz[x] = 1;
     54     forson(x, i) {
     55         int y = edge[i].v;
     56         if(y == f) continue;
     57         d[y] = d[x] + edge[i].len;
     58         DFS_1(y, x);
     59         siz[x] += siz[y];
     60         if(siz[y] > siz[son[x]]) {
     61             son[x] = y;
     62         }
     63     }
     64     return;
     65 }
     66 
     67 void DFS_2(int x, int f) { /// get top id pos
     68     pos[x] = ++num;
     69     top[x] = f;
     70     Sum[num] = d[x] - d[fa[x]];
     71     if(son[x]) {
     72         DFS_2(son[x], f);
     73     }
     74     forson(x, i) {
     75         int y = edge[i].v;
     76         if(y == fa[x] || y == son[x]) continue;
     77         DFS_2(y, y);
     78     }
     79     return;
     80 }
     81 
     82 inline int lca(int x, int y) {
     83     while(top[x] != top[y]) {
     84         if(deep[top[x]] > deep[top[y]]) {
     85             x = fa[top[x]];
     86         }
     87         else {
     88             y = fa[top[y]];
     89         }
     90     }
     91     return deep[x] < deep[y] ? x : y;
     92 }
     93 
     94 inline LL dis(int x, int y) {
     95     return d[x] + d[y] - 2 * d[lca(x, y)];
     96 }
     97 
     98 inline void pushdown(int l, int r, int o) {
     99     if(tag[o] != -1) {
    100         if(tag[o] == 0) {
    101             sum[o << 1] = sum[o << 1 | 1] = 0;
    102         }
    103         else {
    104             int mid = (l + r) >> 1;
    105             sum[o << 1] = Sum[mid] - Sum[l - 1];
    106             sum[o << 1 | 1] = Sum[r] - Sum[mid];
    107         }
    108         tag[o << 1] = tag[o << 1 | 1] = tag[o];
    109         tag[o] = -1;
    110     }
    111     return;
    112 }
    113 
    114 void Add(int L, int R, int l, int r, int o) {
    115     if(L <= l && r <= R) {
    116         sum[o] = Sum[r] - Sum[l - 1];
    117         tag[o] = 1;
    118         return;
    119     }
    120     int mid = (l + r) >> 1;
    121     pushdown(l, r, o);
    122     if(L <= mid) Add(L, R, l, mid, o << 1);
    123     if(mid < R) Add(L, R, mid + 1, r, o << 1 | 1);
    124     sum[o] = sum[o << 1] + sum[o << 1 | 1];
    125     return;
    126 }
    127 
    128 LL ask(int L, int R, int l, int r, int o) {
    129     if(L <= l && r <= R) {
    130         return sum[o];
    131     }
    132     int mid = (l + r) >> 1;
    133     pushdown(l, r, o);
    134     LL ans = 0;
    135     if(L <= mid) {
    136         ans += ask(L, R, l, mid, o << 1);
    137     }
    138     if(mid < R) {
    139         ans += ask(L, R, mid + 1, r, o << 1 | 1);
    140     }
    141     return ans;
    142 }
    143 
    144 inline void Add(int x, int y) {
    145     while(top[x] != top[y]) {
    146         if(deep[top[x]] > deep[top[y]]) {
    147             std::swap(x, y);
    148         }
    149         Add(pos[top[y]], pos[y], 1, n, 1);
    150         y = fa[top[y]];
    151     }
    152     if(deep[x] > deep[y]) std::swap(x, y);
    153     if(x != y) Add(pos[x] + 1, pos[y], 1, n, 1);
    154     return;
    155 }
    156 
    157 inline LL ask(int x, int y) {
    158     LL ans = 0;
    159     while(top[x] != top[y]) {
    160         if(deep[top[x]] > deep[top[y]]) {
    161             std::swap(x, y);
    162         }
    163         ans += ask(pos[top[y]], pos[y], 1, n, 1);
    164         y = fa[top[y]];
    165     }
    166     if(deep[x] > deep[y]) std::swap(x, y);
    167     if(x != y) ans += ask(pos[x] + 1, pos[y], 1, n, 1);
    168     return ans;
    169 }
    170 
    171 inline void clear() {
    172     memset(e + 1, 0, n * sizeof(int));
    173     memset(son + 1, 0, n * sizeof(int));
    174     tp = 1;
    175     num = 0;
    176     return;
    177 }
    178 /*
    179 1
    180 5
    181 1 2 1
    182 2 3 3
    183 3 4 3
    184 1 5 9
    185 2
    186 1 5 5
    187 2 3 8
    188 */
    189 
    190 namespace Line {
    191     LL ta[N], ta2[N];
    192     inline LL ask(int i) {
    193         LL ans = -INF;
    194         for(; i; i -= i & (-i)) {
    195             ans = std::max(ans, ta[i]);
    196         }
    197         return ans;
    198     }
    199     inline void Add(int i, LL v) {
    200         for(; i <= n; i += i & (-i)) {
    201             ta[i] = std::max(ta[i], v);
    202         }
    203         return;
    204     }
    205     inline LL ask2(int i) {
    206         LL ans = -INF;
    207         for(; i; i -= i & (-i)) {
    208             ans = std::max(ans, ta2[i]);
    209         }
    210         return ans;
    211     }
    212     inline void Add2(int i, LL v) {
    213         for(; i <= n; i += i & (-i)) {
    214             ta2[i] = std::max(ta2[i], v);
    215         }
    216         return;
    217     }
    218     inline void solve() {
    219         for(int i = 1; i <= n; i++) ta2[i] = ta[i] = -INF;
    220         LL ans = -INF;
    221         std::sort(node + 1, node + m + 1);
    222         for(int i = m; i >= 1; i--) {
    223             LL temp = ask(node[i].y - 1);
    224             if(temp != -INF) {
    225                 ans = std::max(ans, temp + node[i].val - Sum[node[i].y]);
    226             }
    227             temp = ask2(node[i].y);
    228             if(temp != -INF) {
    229                 ans = std::max(ans, temp + node[i].val);
    230             }
    231             Add(node[i].x, node[i].val + Sum[node[i].x]);
    232             Add2(node[i].y, node[i].val + Sum[node[i].x] - Sum[node[i].y]);
    233         }
    234         if(ans == -INF) puts("F");
    235         else {
    236             printf("%lld\n", ans);
    237         }
    238         return;
    239     }
    240 }
    241 
    242 namespace C0 {
    243     int xx;
    244     LL Ans, X[N];
    245     std::vector<int> v[N];
    246     namespace seg {
    247         int cnt[M];
    248         LL sum[M];
    249         void insert(int p, int v, int l, int r, int &o) {
    250             if(!o) {
    251                 o = ++tot;
    252                 sum[o] = cnt[o] = ls[o] = rs[o] = 0;
    253             }
    254             if(l == r) {
    255                 sum[o] += v * X[r];
    256                 cnt[o] += v;
    257                 return;
    258             }
    259             int mid = (l + r) >> 1;
    260             if(p <= mid) {
    261                 insert(p, v, l, mid, ls[o]);
    262             }
    263             else {
    264                 insert(p, v, mid + 1, r, rs[o]);
    265             }
    266             sum[o] = sum[ls[o]] + sum[rs[o]];
    267             cnt[o] = cnt[ls[o]] + cnt[rs[o]];
    268             return;
    269         }
    270         LL ask(int k, int l, int r, int o) {
    271             if(l == r) {
    272                 return k * X[r];
    273             }
    274             int mid = (l + r) >> 1;
    275             if(k <= cnt[rs[o]]) {
    276                 return ask(k, mid + 1, r, rs[o]);
    277             }
    278             else {
    279                 return ask(k - cnt[rs[o]], l, mid, ls[o]) + sum[rs[o]];
    280             }
    281         }
    282         inline LL Ask(int x) {
    283             if(cnt[rt[x]] < 2) return -INF;
    284             return ask(2, 1, xx, rt[x]);
    285         }
    286         int merge(int x, int y) {
    287             if(!x || !y) return x | y;
    288             sum[x] += sum[y];
    289             cnt[x] += cnt[y];
    290             ls[x] = merge(ls[x], ls[y]);
    291             rs[x] = merge(rs[x], rs[y]);
    292             return x;
    293         }
    294         inline void Merge(int x, int y) {
    295             rt[x] = merge(rt[x], rt[y]);
    296             return;
    297         }
    298     }
    299     void DFS(int x, int f) {
    300         forson(x, i) {
    301             int y = edge[i].v;
    302             if(y == f) continue;
    303             DFS(y, x);
    304             Ans = std::max(Ans, seg::Ask(y));
    305             seg::Merge(x, y);
    306         }
    307         for(int i = 0; i < (int)v[x].size(); i++) {
    308             int t = v[x][i];
    309             if(t > 0) {
    310                 seg::insert(t, 1, 1, xx, rt[x]);
    311             }
    312             else {
    313                 seg::insert(-t, -1, 1, xx, rt[x]);
    314             }
    315         }
    316         return;
    317     }
    318     inline void solve() {
    319         memset(rt + 1, 0, n * sizeof(int));
    320         tot = 0;
    321         Ans = -INF;
    322         for(int i = 1; i <= n; i++) v[i].clear();
    323         for(int i = 1; i <= m; i++) {
    324             X[i] = node[i].val;
    325         }
    326         std::sort(X + 1, X + m + 1);
    327         xx = std::unique(X + 1, X + m + 1) - X - 1;
    328         for(int i = 1; i <= m; i++) {
    329             int val = std::lower_bound(X + 1, X + xx + 1, node[i].val) - X;
    330             int x = node[i].x, y = node[i].y, z = lca(node[i].x, node[i].y);
    331             v[x].push_back(val);
    332             v[y].push_back(val);
    333             v[z].push_back(-val);
    334             v[z].push_back(-val);
    335         }
    336         DFS(1, 0);
    337         if(Ans == -INF) puts("F");
    338         else printf("%lld\n", Ans);
    339         return;
    340     }
    341 }
    342 
    343 namespace tbf {
    344     LL d2[N], Ans;
    345     int Top, stk[N], stk2[N], Top2, faa[N][20];
    346     std::vector<int> vx[N], v[N];
    347     LL dis2(int x, int y) {
    348         return d2[x] + d2[y] - 2 * d2[lca(x, y)];
    349     }
    350     void DFS_3(int x, int f) { /// get dis2
    351         forson(x, i) {
    352             int y = edge[i].v;
    353             if(y == f) continue;
    354             d2[y] = d2[x] + edge[i].len * edge[i].vis;
    355             DFS_3(y, x);
    356         }
    357         return;
    358     }
    359     bool DFS_4(int x, int f, int t) { /// visit a link
    360         if(x == t) {
    361             Top = 0;
    362             return true;
    363         }
    364         forson(x, i) {
    365             int y = edge[i].v;
    366             if(y == f) {
    367                 continue;
    368             }
    369             if(DFS_4(y, x, t)) {
    370                 edge[i].vis = edge[i ^ 1].vis = 1;
    371                 stk[++Top] = i;
    372                 return true;
    373             }
    374         }
    375         return false;
    376     }
    377     namespace seg {
    378         int sum[M];
    379         void insert(int p, int v, int l, int r, int &o) {
    380             if(!o) {
    381                 o = ++tot;
    382                 ls[o] = rs[o] = sum[o] = 0;
    383             }
    384             if(l == r) {
    385                 sum[o] += v;
    386                 return;
    387             }
    388             int mid = (l + r) >> 1;
    389             if(p <= mid) insert(p, v, l, mid, ls[o]);
    390             else insert(p, v, mid + 1, r, rs[o]);
    391             sum[o] = sum[ls[o]] + sum[rs[o]];
    392             return;
    393         }
    394         void solve(int l, int r, int o) {
    395             if(l == r) {
    396                 stk2[++Top2] = r;
    397                 return;
    398             }
    399             int mid = (l + r) >> 1;
    400             if(sum[ls[o]]) {
    401                 solve(l, mid, ls[o]);
    402             }
    403             if(sum[rs[o]]) {
    404                 solve(mid + 1, r, rs[o]);
    405             }
    406             return;
    407         }
    408         int merge(int x, int y) {
    409             if(!x || !y) return x | y;
    410             sum[x] += sum[y];
    411             ls[x] = merge(ls[x], ls[y]);
    412             rs[x] = merge(rs[x], rs[y]);
    413             return x;
    414         }
    415     }
    416 
    417     void DFS_5(int x, int f) {
    418         forson(x, i) {
    419             int y = edge[i].v;
    420             if(y == f) continue;
    421             DFS_5(y, x);
    422             Top2 = 0;
    423             seg::solve(1, m, rt[y]);
    424             for(int j = 0; j < (int)vx[y].size(); j++) {
    425                 int z = vx[y][j];
    426                 /// link z
    427                 DFS_4(node[z].x, 0, node[z].y);
    428                 DFS_3(1, 0);
    429                 for(int k = 1; k <= Top2; k++) {
    430                     int w = stk2[k]; /// link w
    431                     if(w == z) continue;
    432                     Ans = std::max(Ans, node[z].val + node[w].val - dis2(node[w].x, node[w].y));
    433                 }
    434                 while(Top) {
    435                     edge[stk[Top]].vis = edge[stk[Top] ^ 1].vis = 0;
    436                     Top--;
    437                 }
    438             }
    439             rt[x] = seg::merge(rt[x], rt[y]);
    440         }
    441         /// insert
    442         for(int i = 0; i < (int)v[x].size(); i++) {
    443             int t = v[x][i];
    444             if(t > 0) {
    445                 seg::insert(t, 1, 1, m, rt[x]);
    446             }
    447             else {
    448                 seg::insert(-t, -1, 1, m, rt[x]);
    449             }
    450         }
    451         return;
    452     }
    453     void DFS_6(int x, int f) {
    454         faa[x][0] = f;
    455         forson(x, i) {
    456             int y = edge[i].v;
    457             if(y == f) continue;
    458             DFS_6(y, x);
    459         }
    460         return;
    461     }
    462     inline void prework() {
    463         for(int j = 1; j <= pw[n]; j++) {
    464             for(int i = 1; i <= n; i++) {
    465                 faa[i][j] = faa[faa[i][j - 1]][j - 1];
    466             }
    467         }
    468         return;
    469     }
    470     inline int Find(int x, int z) {
    471         int t = pw[n];
    472         while(t >= 0 && fa[x] != z) {
    473             if(deep[faa[x][t]] > deep[z]) {
    474                 x = faa[x][t];
    475             }
    476             t--;
    477         }
    478         return x;
    479     }
    480     inline void solve() {
    481         tot = 0;
    482         Ans = -INF;
    483         memset(rt + 1, 0, n * sizeof(int));
    484         for(int i = 1; i <= n; i++) {
    485             v[i].clear();
    486             vx[i].clear();
    487         }
    488         DFS_6(1, 0);
    489         prework();
    490         for(int i = 1; i <= m; i++) {
    491             int x = node[i].x, y = node[i].y, z = lca(x, y);
    492             v[x].push_back(i);
    493             v[y].push_back(i);
    494             v[z].push_back(-i);
    495             v[z].push_back(-i);
    496             if(x != z) {
    497                 int xx = Find(x, z);
    498                 vx[xx].push_back(i);
    499             }
    500             if(y != z) {
    501                 int yy = Find(y, z);
    502                 vx[yy].push_back(i);
    503             }
    504         }
    505         DFS_5(1, 0);
    506         if(Ans == -INF) puts("F");
    507         else printf("%lld\n", Ans);
    508         return;
    509     }
    510 } /** namespace tbf */
    511 
    512 inline void solve() {
    513 
    514     sum[1] = tag[1] = 0;
    515 
    516     scanf("%d", &n);
    517     LL z;
    518     bool FLAG = 1, c0 = 1;
    519     for(int i = 1, x, y; i < n; i++) {
    520         scanf("%d%d%lld", &x, &y, &z);
    521         add(x, y, z);
    522         add(y, x, z);
    523         if(z) c0 = 0;
    524         if(y != x + 1) {
    525             FLAG = 0;
    526         }
    527     }
    528 
    529     DFS_1(1, 0);
    530     DFS_2(1, 1);
    531 
    532     for(int i = 1; i <= n; i++) {
    533         Sum[i] += Sum[i - 1];
    534     }
    535 
    536     scanf("%d", &m);
    537     for(int i = 1; i <= m; i++) {
    538         scanf("%d%d%lld", &node[i].x, &node[i].y, &node[i].z);
    539         if(node[i].x > node[i].y) std::swap(node[i].x, node[i].y);
    540         else if(node[i].x == node[i].y) {
    541             m--;
    542             i--;
    543         }
    544         node[i].val = dis(node[i].x, node[i].y) - node[i].z;
    545         //printf("node %d [%d %d] val = %lld \n", i, node[i].x, node[i].y, node[i].val);
    546     }
    547     // solve
    548 
    549     tbf::solve();
    550     clear();
    551     return;
    552 
    553     if(FLAG) {
    554         Line::solve();
    555         clear();
    556         return;
    557     }
    558     if(c0) {
    559         C0::solve();
    560         clear();
    561         return;
    562     }
    563 
    564     if(m > 300) {
    565         tbf::solve();
    566         clear();
    567         return;
    568     }
    569 
    570     LL ans = -INF;
    571     for(int i = 1; i < m; i++) {
    572         Add(node[i].x, node[i].y);
    573         for(int j = i + 1; j <= m; j++) {
    574             /// choose i j
    575             LL Val = ask(node[j].x, node[j].y);
    576             //printf("Val = %lld \n", Val);
    577             if(Val) {
    578                 ans = std::max(ans, node[i].val + node[j].val - Val);
    579             }
    580         }
    581         tag[1] = sum[1] = 0;
    582     }
    583     if(ans == -INF) {
    584         puts("F");
    585     }
    586     else {
    587         printf("%lld\n", ans);
    588     }
    589     clear();
    590     return;
    591 }
    592 
    593 int main() {
    594 
    595     for(int i = 2; i < N; i++) pw[i] = pw[i >> 1] + 1;
    596 
    597     int T;
    598     scanf("%d", &T);
    599     while(T--) solve();
    600     return 0;
    601 }

20分真暴力代码

接下来是S1的部分分：所有lca全部不同。

![1332167-20190412105002710-1709940313.png][]

实际上(参考yww的代码)我们要维护两个东西，一个是val最大值，一个是val + d\[lca\]的最大值。然后更新的时候，把线段树交错更新。

也就是说左儿子(较浅)的val + 右儿子(较深)的(val + d\[lca\])然后减去红点的深度。

然后我们要在插入和merge的同时更新。注意到我们还有一个删除操作，x子树搞完之后，深度大于等于x的全部失效，也就是我们要把线段树右边的一段全部清除。

DFS那里插入删除merge的顺序非常重要....反正我试了很久才搞对顺序。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
      2 
      3 #define forson(x, i) for(int i = e[x]; i; i = edge[i].nex)
      4 
      5 typedef long long LL;
      6 const int N = 100010;
      7 const LL INF = 4e18;
      8 
      9 struct Edge {
     10     int nex, v;
     11     LL len;
     12 }edge[N << 1]; int tp = 1;
     13 
     14 struct Node {
     15     int x, y, w;
     16     LL val, z;
     17 }node[N];
     18 
     19 int e[N], num2, pos2[N], ST[N][20], pw[N], deep[N], n, m, fa[N];
     20 LL d[N];
     21 std::bitset<N> visLca;
     22 
     23 inline void add(int x, int y, LL z) {
     24     tp++;
     25     edge[tp].v = y;
     26     edge[tp].len = z;
     27     edge[tp].nex = e[x];
     28     e[x] = tp;
     29     return;
     30 }
     31 
     32 inline void clear() {
     33     memset(e + 1, 0, n * sizeof(int));
     34     visLca.reset();
     35     tp = 1;
     36     num2 = 0;
     37     return;
     38 }
     39 
     40 void DFS(int x, int f) {
     41     pos2[x] = ++num2;
     42     ST[num2][0] = x;
     43     deep[x] = deep[f] + 1;
     44     fa[x] = f;
     45     forson(x, i) {
     46         int y = edge[i].v;
     47         if(y == f) {
     48             continue;
     49         }
     50         d[y] = d[x] + edge[i].len;
     51         DFS(y, x);
     52         ST[++num2][0] = x;
     53     }
     54     return;
     55 }
     56 
     57 inline void prework() {
     58     for(int j = 1; j <= pw[num2]; j++) {
     59         for(int i = 1; i + (1 << j) - 1 <= num2; i++) {
     60             if(deep[ST[i][j - 1]] < deep[ST[i + (1 << (j - 1))][j - 1]]) {
     61                 ST[i][j] = ST[i][j - 1];
     62             }
     63             else {
     64                 ST[i][j] = ST[i + (1 << (j - 1))][j - 1];
     65             }
     66         }
     67     }
     68     return;
     69 }
     70 
     71 inline int lca(int x, int y) {
     72     x = pos2[x];
     73     y = pos2[y];
     74     if(x > y) std::swap(x, y);
     75     int t = pw[y - x + 1];
     76     if(deep[ST[x][t]] < deep[ST[y - (1 << t) + 1][t]]) {
     77         return ST[x][t];
     78     }
     79     else {
     80         return ST[y - (1 << t) + 1][t];
     81     }
     82 }
     83 
     84 inline LL dis(int x, int y) {
     85     return d[x] + d[y] - 2 * d[lca(x, y)];
     86 }
     87 
     88 namespace Sone { /// lca != lca
     89     LL Ans;
     90     int rt[N];
     91     std::vector<int> v[N];
     92     namespace seg {
     93         const int M = 10000010;
     94 
     95         int ls[M], rs[M], tot;
     96         LL large[M], largeD[M];
     97 
     98         inline void pushup(int o) {
     99             large[o] = std::max(large[ls[o]], large[rs[o]]);
    100             largeD[o] = std::max(largeD[ls[o]], largeD[rs[o]]);
    101             return;
    102         }
    103         void insert(int p, LL v, LL v2, LL v3, int l, int r, int &o) {
    104             if(!o) {
    105                 o = ++tot;
    106                 ls[o] = rs[o] = 0;
    107                 large[o] = largeD[o] = -INF;
    108             }
    109             if(l == r) {
    110                 large[o] = std::max(large[o], v);
    111                 largeD[o] = std::max(largeD[o], v + v2);
    112                 return;
    113             }
    114             int mid = (l + r) >> 1;
    115             if(p <= mid) {
    116                 Ans = std::max(Ans, largeD[rs[o]] + v - v3);
    117                 insert(p, v, v2, v3, l, mid, ls[o]);
    118             }
    119             else {
    120                 Ans = std::max(Ans, large[ls[o]] + v + v2 - v3);
    121                 insert(p, v, v2, v3, mid + 1, r, rs[o]);
    122             }
    123             pushup(o);
    124             return;
    125         }
    126         int merge(int x, int y, LL v) {
    127             //printf("merge x = %d y = %d v = %lld \n", x, y, v);
    128             if(!x || !y) return x | y;
    129             Ans = std::max(Ans, std::max(large[ls[x]] + largeD[rs[y]], large[ls[y]] + largeD[rs[x]]) - v);
    130             large[x] = std::max(large[x], large[y]);
    131             largeD[x] = std::max(largeD[x], largeD[y]);
    132             ls[x] = merge(ls[x], ls[y], v);
    133             rs[x] = merge(rs[x], rs[y], v);
    134             return x;
    135         }
    136         void del(int p, int l, int r, int o) {
    137             if(!o) {
    138                 return;
    139             }
    140             if(l == r) {
    141                 large[o] = largeD[o] = -INF;
    142                 return;
    143             }
    144             int mid = (l + r) >> 1;
    145             if(p <= mid) {
    146                 large[rs[o]] = largeD[rs[o]] = -INF;
    147                 del(p, l, mid, ls[o]);
    148             }
    149             else {
    150                 del(p, mid + 1, r, rs[o]);
    151             }
    152             pushup(o);
    153             return;
    154         }
    155     }
    156 
    157     void DFS_1(int x, int f) {
    158         //printf("x = %d \n", x);
    159         for(int i = 0; i < (int)v[x].size(); i++) {
    160             int t = v[x][i];
    161             //printf("x = %d insert p = %d w = %d  v1 = %lld  v2 = %lld \n", x, deep[node[t].w], node[t].w, node[t].val, d[node[t].w]);
    162             seg::insert(deep[node[t].w], node[t].val, d[node[t].w], d[x], 1, n, rt[x]);
    163         }
    164         forson(x, i) {
    165             int y = edge[i].v;
    166             if(y == f) continue;
    167             //printf("y = %d \n", y);
    168             DFS_1(y, x);
    169             //printf("merge %d -> %d \n", x, y);
    170             seg::del(deep[x], 1, n, rt[y]);
    171             rt[x] = seg::merge(rt[x], rt[y], d[x]);
    172             //printf("Ans = %lld \n", Ans);
    173         }
    174         return;
    175     }
    176 
    177     inline void solve() {
    178         seg::tot = 0;
    179         seg::large[0] = seg::largeD[0] = -INF;
    180         Ans = -INF;
    181         memset(rt + 1, 0, n * sizeof(int));
    182         for(int i = 1; i <= n; i++) v[i].clear();
    183 
    184         for(int i = 1; i <= m; i++) {
    185             int x = node[i].x, y = node[i].y, z = node[i].w;
    186             if(x != z) {
    187                 v[x].push_back(i);
    188             }
    189             if(y != z) {
    190                 v[y].push_back(i);
    191             }
    192         }
    193 
    194         DFS_1(1, 0);
    195         if(Ans < (LL)(-3e18)) puts("F");
    196         else printf("%lld\n", Ans);
    197         return;
    198     }
    199 }
    200 
    201 namespace Stwo { /// lca = 1
    202     inline void solve() {
    203 
    204         return;
    205     }
    206 }
    207 
    208 inline void solve() {
    209     scanf("%d", &n);
    210     LL z;
    211     for(int i = 1, x, y; i < n; i++) {
    212         scanf("%d%d%lld", &x, &y, &z);
    213         add(x, y, z);
    214         add(y, x, z);
    215     }
    216 
    217     DFS(1, 0);
    218     prework();
    219 
    220     scanf("%d", &m);
    221     bool S1 = true, S2 = true;
    222     int lastLca = -1;
    223     for(int i = 1, x, y; i <= m; i++) {
    224         scanf("%d%d%lld", &x, &y, &z);
    225         node[i].x = x;
    226         node[i].y = y;
    227         node[i].z = z;
    228         node[i].val = dis(x, y) - z;
    229         int temp = lca(x, y);
    230         if(lastLca == -1) lastLca = temp;
    231         else if(lastLca != temp) S2 = false;
    232         if(visLca[temp]) S1 = false;
    233         else visLca.set(temp);
    234         node[i].w = temp;
    235     }
    236 
    237     if(S1) {
    238         Sone::solve();
    239         return;
    240     }
    241     if(S2) {
    242         Stwo::solve();
    243         return;
    244     }
    245 
    246     return;
    247 }
    248 
    249 int main() {
    250 
    251     freopen("in.in", "r", stdin);
    252     freopen("my.out", "w", stdout);
    253 
    254     for(int i = 2; i < N; i++) pw[i] = pw[i >> 1] + 1;
    255 
    256     int T;
    257     scanf("%d", &T);
    258     while(T--) {
    259         solve();
    260         if(T) clear();
    261     }
    262     return 0;
    263 }

15分S1代码

接下来是S2的lca全部为1的部分分。

继续抄题解。

![1332167-20190412194837597-1423067144.png][]

我的理解是，首先把2 \* 总价值转化成链长之和 - 代价之和 + 蓝点距离 + 绿点距离。我们尝试新建两个点来表示出这个东西。

首先把蓝点距离转化成蓝a深度 + 蓝b深度 - 2 \* 红点深度。

对于一条链a，我们在绿a处挂上一个节点绿a'，使得它到绿a的距离为链长 - 代价 + 蓝a深度。

然后我们发现，这样两个附加点的距离正好凑出了上面那个2 \* 总价值，只要再减去2 \* 红点深度就行了。

![1332167-20190412195722884-1286743983.png][]

有这个结论是因为**边权非负**。那么我们新加的边不是有一堆负权吗？为什么成立呢？

因为我们可以给这些新加的边(假装加上了)加上一个很大的正值来达到非负。为什么这个方法在一般的树上不适用呢？因为我们不知道直径上有多少条边加了这个大正值。但是本题中会有恰两条边加上这个正值。

所以做法就出来了。具体来说，我们DFS这棵树，然后在每个蓝a处把绿a'加入点集，同理在绿a处把蓝a'加入点集。

然后合并点集的同时更新答案。注意当前点为根的时候不能更新，因为可能会把蓝a'和绿a'的距离算入答案。也没必要更新，因为根不可能作为红点。

注意只需要挂可能成为蓝a的对应的绿a'，就是说一条链直上直下的时候有一个点不用加。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
      2 
      3 #define forson(x, i) for(int i = e[x]; i; i = edge[i].nex)
      4 
      5 using namespace std;
      6 
      7 typedef long long LL;
      8 const int N = 300010;
      9 const LL INF = 4e18;
     10 
     11 struct Edge {
     12     int nex, v;
     13     LL len;
     14 }edge[N << 1]; int tp = 1;
     15 
     16 struct Node {
     17     int x, y, w;
     18     LL val, z;
     19 }node[N];
     20 
     21 struct Data {
     22     int a, b;
     23     Data(int A = 0, int B = 0) : a(A), b(B) {}
     24 }data[N];
     25 
     26 int e[N], num2, pos2[N], ST[N][20], pw[N], deep[N], n, m, fa[N], fr[N];
     27 LL d[N];
     28 std::bitset<N> visLca;
     29 
     30 inline void add(int x, int y, LL z) {
     31     tp++;
     32     edge[tp].v = y;
     33     edge[tp].len = z;
     34     edge[tp].nex = e[x];
     35     e[x] = tp;
     36     return;
     37 }
     38 
     39 inline void clear() {
     40     memset(e + 1, 0, n * sizeof(int));
     41     visLca.reset();
     42     tp = 1;
     43     num2 = 0;
     44     return;
     45 }
     46 
     47 void DFS(int x, int f) {
     48     pos2[x] = ++num2;
     49     ST[num2][0] = x;
     50     deep[x] = deep[f] + 1;
     51     fa[x] = f;
     52     forson(x, i) {
     53         int y = edge[i].v;
     54         if(y == f) {
     55             continue;
     56         }
     57         d[y] = d[x] + edge[i].len;
     58         DFS(y, x);
     59         ST[++num2][0] = x;
     60     }
     61     return;
     62 }
     63 
     64 inline void prework() {
     65     for(int j = 1; j <= pw[num2]; j++) {
     66         for(int i = 1; i + (1 << j) - 1 <= num2; i++) {
     67             if(deep[ST[i][j - 1]] < deep[ST[i + (1 << (j - 1))][j - 1]]) {
     68                 ST[i][j] = ST[i][j - 1];
     69             }
     70             else {
     71                 ST[i][j] = ST[i + (1 << (j - 1))][j - 1];
     72             }
     73         }
     74     }
     75     return;
     76 }
     77 
     78 inline int lca(int x, int y) {
     79     x = pos2[fr[x]];
     80     y = pos2[fr[y]];
     81     if(x > y) std::swap(x, y);
     82     int t = pw[y - x + 1];
     83     if(deep[ST[x][t]] < deep[ST[y - (1 << t) + 1][t]]) {
     84         return ST[x][t];
     85     }
     86     else {
     87         return ST[y - (1 << t) + 1][t];
     88     }
     89 }
     90 
     91 inline LL dis(int x, int y) {
     92     if(!x || !y) return -INF;
     93     if(x > n && (x - n + 1) / 2 == (y - n + 1) / 2) return -INF;
     94     //if(x > n) printf("dis %d %d = %lld \n", x, y, d[x] + d[y] - 2 * d[lca(x, y)]);
     95     return d[x] + d[y] - 2 * d[lca(x, y)];
     96 }
     97 
     98 namespace Sone { /// lca != lca
     99     LL Ans;
    100     int rt[N];
    101     std::vector<int> v[N];
    102     namespace seg {
    103         const int M = 10000010;
    104 
    105         int ls[M], rs[M], tot;
    106         LL large[M], largeD[M];
    107 
    108         inline void pushup(int o) {
    109             large[o] = std::max(large[ls[o]], large[rs[o]]);
    110             largeD[o] = std::max(largeD[ls[o]], largeD[rs[o]]);
    111             return;
    112         }
    113         void insert(int p, LL v, LL v2, LL v3, int l, int r, int &o) {
    114             if(!o) {
    115                 o = ++tot;
    116                 ls[o] = rs[o] = 0;
    117                 large[o] = largeD[o] = -INF;
    118             }
    119             if(l == r) {
    120                 large[o] = std::max(large[o], v);
    121                 largeD[o] = std::max(largeD[o], v + v2);
    122                 return;
    123             }
    124             int mid = (l + r) >> 1;
    125             if(p <= mid) {
    126                 Ans = std::max(Ans, largeD[rs[o]] + v - v3);
    127                 insert(p, v, v2, v3, l, mid, ls[o]);
    128             }
    129             else {
    130                 Ans = std::max(Ans, large[ls[o]] + v + v2 - v3);
    131                 insert(p, v, v2, v3, mid + 1, r, rs[o]);
    132             }
    133             pushup(o);
    134             return;
    135         }
    136         int merge(int x, int y, LL v) {
    137             //printf("merge x = %d y = %d v = %lld \n", x, y, v);
    138             if(!x || !y) return x | y;
    139             Ans = std::max(Ans, std::max(large[ls[x]] + largeD[rs[y]], large[ls[y]] + largeD[rs[x]]) - v);
    140             large[x] = std::max(large[x], large[y]);
    141             largeD[x] = std::max(largeD[x], largeD[y]);
    142             ls[x] = merge(ls[x], ls[y], v);
    143             rs[x] = merge(rs[x], rs[y], v);
    144             return x;
    145         }
    146         void del(int p, int l, int r, int o) {
    147             if(!o) {
    148                 return;
    149             }
    150             if(l == r) {
    151                 large[o] = largeD[o] = -INF;
    152                 return;
    153             }
    154             int mid = (l + r) >> 1;
    155             if(p <= mid) {
    156                 large[rs[o]] = largeD[rs[o]] = -INF;
    157                 del(p, l, mid, ls[o]);
    158             }
    159             else {
    160                 del(p, mid + 1, r, rs[o]);
    161             }
    162             pushup(o);
    163             return;
    164         }
    165     }
    166 
    167     void DFS_1(int x, int f) {
    168         //printf("x = %d \n", x);
    169         for(int i = 0; i < (int)v[x].size(); i++) {
    170             int t = v[x][i];
    171             //printf("x = %d insert p = %d w = %d  v1 = %lld  v2 = %lld \n", x, deep[node[t].w], node[t].w, node[t].val, d[node[t].w]);
    172             seg::insert(deep[node[t].w], node[t].val, d[node[t].w], d[x], 1, n, rt[x]);
    173         }
    174         forson(x, i) {
    175             int y = edge[i].v;
    176             if(y == f) continue;
    177             //printf("y = %d \n", y);
    178             DFS_1(y, x);
    179             //printf("merge %d -> %d \n", x, y);
    180             seg::del(deep[x], 1, n, rt[y]);
    181             rt[x] = seg::merge(rt[x], rt[y], d[x]);
    182             //printf("Ans = %lld \n", Ans);
    183         }
    184         return;
    185     }
    186 
    187     inline void solve() {
    188         seg::tot = 0;
    189         seg::large[0] = seg::largeD[0] = -INF;
    190         Ans = -INF;
    191         memset(rt + 1, 0, n * sizeof(int));
    192         for(int i = 1; i <= n; i++) v[i].clear();
    193 
    194         for(int i = 1; i <= m; i++) {
    195             int x = node[i].x, y = node[i].y, z = node[i].w;
    196             if(x != z) {
    197                 v[x].push_back(i);
    198             }
    199             if(y != z) {
    200                 v[y].push_back(i);
    201             }
    202         }
    203 
    204         DFS_1(1, 0);
    205         if(Ans < (LL)(-3e18)) puts("F");
    206         else printf("%lld\n", Ans);
    207         return;
    208     }
    209 }
    210 
    211 namespace Stwo { /// lca = 1
    212     /*Edge EDGE[N << 1]; int TP;
    213     int E[N], use[N], Time, fr[N];
    214     inline void ADD(int x, int y, LL z) {
    215         TP++;
    216         EDGE[TP].v = y;
    217         EDGE[TP].len = z;
    218         EDGE[TP].nex = E[x];
    219         E[x] = TP;
    220         return;
    221     }
    222     inline void work(int x) {
    223         if(use[x] != Time) {
    224             use[x] = Time;
    225             E[x] = 0;
    226             ? = ?;
    227         }
    228         return;
    229     }*/
    230     std::vector<int> v[N];
    231     LL Ans;
    232 
    233     inline void update(Data &x, const Data &y, const LL &v) {
    234         //printf("update v = %lld \n", v);
    235         LL d12 = dis(x.a, x.b), d34 = dis(y.a, y.b);
    236         LL d13 = dis(x.a, y.a), d14 = dis(x.a, y.b);
    237         LL d23 = dis(x.b, y.a), d24 = dis(x.b, y.b);
    238         Ans = std::max(Ans, std::max(std::max(d13, d14), std::max(d23, d24)) - v);
    239         int xa = x.a, xb = x.b;
    240         if(d34 > d12) {
    241             x = y;
    242             d12 = d34;
    243         }
    244         if(d13 > d12) {
    245             x = Data(xa, y.a);
    246             d12 = d13;
    247         }
    248         if(d14 > d12) {
    249             x = Data(xa, y.b);
    250             d12 = d14;
    251         }
    252         if(d23 > d12) {
    253             x = Data(xb, y.a);
    254             d12 = d23;
    255         }
    256         if(d24 > d12) {
    257             x = Data(xb, y.b);
    258         }
    259         if(!x.a) x = y;
    260         //printf("Ans = %lld \n", Ans);
    261         return;
    262     }
    263 
    264     inline void update(Data &x, const int &a, const LL &v) {
    265         //printf("insert v = %lld \n", v);
    266         LL d1 = dis(x.a, a), d2 = dis(x.b, a), d3 = dis(x.a, x.b);
    267         Ans = std::max(Ans, std::max(d1, d2) - v);
    268         int xa = x.a, xb = x.b;
    269         if(d1 > d3) {
    270             x.b = a;
    271             d3 = d1;
    272         }
    273         if(d2 > d3) {
    274             x = Data(xb, a);
    275         }
    276         if(!x.a) x.a = a;
    277         //printf("Ans = %lld \n", Ans);
    278         return;
    279     }
    280 
    281     void DFS_1(int x, int f) {
    282         forson(x, i) {
    283             int y = edge[i].v;
    284             if(y == f) continue;
    285             DFS_1(y, x);
    286             if(f) update(data[x], data[y], d[x] << 1);
    287             //printf("data x : %d %d \n", data[x].a, data[x].b);
    288         }
    289         if(f) {
    290             for(int i = 0; i < (int)v[x].size(); i++) {
    291                 int t = v[x][i];
    292                 update(data[x], t, d[x] << 1);
    293             }
    294         }
    295         return;
    296     }
    297 
    298     inline void solve() {
    299 
    300         //printf("S2 inside \n");
    301 
    302         for(int i = 1; i <= n; i++) {
    303             v[i].clear();
    304             v[i].resize(0);
    305             data[i].a = data[i].b = 0;
    306         }
    307         Ans = -INF;
    308         for(int i = 1; i <= m; i++) {
    309             int x = node[i].x, y = node[i].y, z = node[i].w;
    310             if(x != z) {
    311                 fr[n + i * 2 - 1] = y;
    312                 d[n + i * 2 - 1] = d[y] + d[x] + node[i].val - node[i].z;
    313                 v[x].push_back(n + i * 2 - 1);
    314                 //printf("%d : d = %lld fr = %d \n", n + i * 2 - 1, d[n + i * 2 - 1], fr[n + i * 2 - 1]);
    315             }
    316             if(y != z) {
    317                 fr[n + i * 2] = x;
    318                 d[n + i * 2] = d[x] + d[y] + node[i].val - node[i].z;
    319                 v[y].push_back(n + i * 2);
    320                 //printf("%d : d = %lld fr = %d \n", n + i * 2, d[n + i * 2], fr[n + i * 2]);
    321             }
    322         }
    323         //puts("");
    324         DFS_1(1, 0);
    325 
    326         if(Ans < (LL)-3e18) puts("F");
    327         else printf("%lld\n", Ans >> 1);
    328         return;
    329     }
    330 }
    331 
    332 inline void solve() {
    333     scanf("%d", &n);
    334     for(int i = 1; i <= n; i++) {
    335         fr[i] = i;
    336     }
    337     LL z;
    338     for(int i = 1, x, y; i < n; i++) {
    339         scanf("%d%d%lld", &x, &y, &z);
    340         add(x, y, z);
    341         add(y, x, z);
    342     }
    343 
    344     DFS(1, 0);
    345     prework();
    346 
    347     scanf("%d", &m);
    348     bool S1 = true, S2 = true;
    349     int lastLca = -1;
    350     for(int i = 1, x, y; i <= m; i++) {
    351         scanf("%d%d%lld", &x, &y, &z);
    352         node[i].x = x;
    353         node[i].y = y;
    354         node[i].z = z;
    355         node[i].val = dis(x, y) - z;
    356         int temp = lca(x, y);
    357         if(lastLca == -1) lastLca = temp;
    358         else if(lastLca != temp) S2 = false;
    359         if(visLca[temp]) S1 = false;
    360         else visLca.set(temp);
    361         node[i].w = temp;
    362     }
    363 
    364     if(S1) {
    365         Sone::solve();
    366         return;
    367     }
    368     if(S2) {
    369         Stwo::solve();
    370         return;
    371     }
    372 
    373     return;
    374 }
    375 
    376 int main() {
    377 
    378     //freopen("in.in", "r", stdin);
    379     //freopen("my.out", "w", stdout);
    380 
    381     for(int i = 2; i < N; i++) pw[i] = pw[i >> 1] + 1;
    382 
    383     int T;
    384     scanf("%d", &T);
    385     while(T--) {
    386         solve();
    387         if(T) clear();
    388     }
    389     return 0;
    390 }

35分S1+S2代码

终于到正解了...考虑两条链如果有交，那么要么是直上直下的交，lca不同；要么是交了一段可能不直上直下的，lca相同。

那么lca不同的所有情况直接调用S1即可。lca相同的情况，可能在很多点相同。此时我们枚举每个点，把以这些点为lca的链都提出来建虚树，套用S2即可。

考虑为什么套用S1的时候不会把本来属于S2的情况算得更优。

注意到一个细节，就是S1中如果两个链加到线段树的同一下标上(lca相同)，我们是不会把这两条链拿去更新答案的。于是S1中更新的就都是lca不同的啦！

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
      2 
      3 #define forson(x, i) for(int i = e[x]; i; i = edge[i].nex)
      4 
      5 typedef long long LL;
      6 const int N = 300010;
      7 const LL INF = 4e18;
      8 
      9 struct Edge {
     10     int nex, v;
     11     LL len;
     12 }edge[N << 1]; int tp = 1;
     13 
     14 struct Node {
     15     int x, y, w;
     16     LL val, z;
     17 }node[N];
     18 
     19 struct Data {
     20     int a, b;
     21     Data(int A = 0, int B = 0) : a(A), b(B) {}
     22 }data[N];
     23 
     24 int e[N], num2, pos2[N], ST[N][20], pw[N], deep[N], n, m, fa[N], fr[N];
     25 LL d[N], Ans;
     26 
     27 inline void add(int x, int y, LL z) {
     28     tp++;
     29     edge[tp].v = y;
     30     edge[tp].len = z;
     31     edge[tp].nex = e[x];
     32     e[x] = tp;
     33     return;
     34 }
     35 
     36 inline void clear() {
     37     memset(e + 1, 0, n * sizeof(int));
     38     tp = 1;
     39     num2 = 0;
     40     return;
     41 }
     42 
     43 void DFS(int x, int f) {
     44     pos2[x] = ++num2;
     45     ST[num2][0] = x;
     46     deep[x] = deep[f] + 1;
     47     fa[x] = f;
     48     forson(x, i) {
     49         int y = edge[i].v;
     50         if(y == f) {
     51             continue;
     52         }
     53         d[y] = d[x] + edge[i].len;
     54         DFS(y, x);
     55         ST[++num2][0] = x;
     56     }
     57     return;
     58 }
     59 
     60 inline void prework() {
     61     for(int j = 1; j <= pw[num2]; j++) {
     62         for(int i = 1; i + (1 << j) - 1 <= num2; i++) {
     63             if(deep[ST[i][j - 1]] < deep[ST[i + (1 << (j - 1))][j - 1]]) {
     64                 ST[i][j] = ST[i][j - 1];
     65             }
     66             else {
     67                 ST[i][j] = ST[i + (1 << (j - 1))][j - 1];
     68             }
     69         }
     70     }
     71     return;
     72 }
     73 
     74 inline int lca(int x, int y) {
     75     x = pos2[fr[x]];
     76     y = pos2[fr[y]];
     77     if(x > y) std::swap(x, y);
     78     int t = pw[y - x + 1];
     79     if(deep[ST[x][t]] < deep[ST[y - (1 << t) + 1][t]]) {
     80         return ST[x][t];
     81     }
     82     else {
     83         return ST[y - (1 << t) + 1][t];
     84     }
     85 }
     86 
     87 inline LL dis(int x, int y) {
     88     if(!x || !y) return -INF;
     89     return d[x] + d[y] - 2 * d[lca(x, y)];
     90 }
     91 
     92 inline bool cmp(const int &a, const int &b) {
     93     return pos2[a] < pos2[b];
     94 }
     95 
     96 namespace Sone { /// lca != lca
     97     int rt[N];
     98     std::vector<int> v[N];
     99     namespace seg {
    100         const int M = 10000010;
    101 
    102         int ls[M], rs[M], tot;
    103         LL large[M], largeD[M];
    104 
    105         inline void pushup(int o) {
    106             large[o] = std::max(large[ls[o]], large[rs[o]]);
    107             largeD[o] = std::max(largeD[ls[o]], largeD[rs[o]]);
    108             return;
    109         }
    110         void insert(int p, LL v, LL v2, LL v3, int l, int r, int &o) {
    111             if(!o) {
    112                 o = ++tot;
    113                 ls[o] = rs[o] = 0;
    114                 large[o] = largeD[o] = -INF;
    115             }
    116             if(l == r) {
    117                 large[o] = std::max(large[o], v);
    118                 largeD[o] = std::max(largeD[o], v + v2);
    119                 return;
    120             }
    121             int mid = (l + r) >> 1;
    122             if(p <= mid) {
    123                 Ans = std::max(Ans, largeD[rs[o]] + v - v3);
    124                 insert(p, v, v2, v3, l, mid, ls[o]);
    125             }
    126             else {
    127                 Ans = std::max(Ans, large[ls[o]] + v + v2 - v3);
    128                 insert(p, v, v2, v3, mid + 1, r, rs[o]);
    129             }
    130             pushup(o);
    131             return;
    132         }
    133         int merge(int x, int y, LL v) {
    134             if(!x || !y) return x | y;
    135             Ans = std::max(Ans, std::max(large[ls[x]] + largeD[rs[y]], large[ls[y]] + largeD[rs[x]]) - v);
    136             large[x] = std::max(large[x], large[y]);
    137             largeD[x] = std::max(largeD[x], largeD[y]);
    138             ls[x] = merge(ls[x], ls[y], v);
    139             rs[x] = merge(rs[x], rs[y], v);
    140             return x;
    141         }
    142         void del(int p, int l, int r, int o) {
    143             if(!o) {
    144                 return;
    145             }
    146             if(l == r) {
    147                 large[o] = largeD[o] = -INF;
    148                 return;
    149             }
    150             int mid = (l + r) >> 1;
    151             if(p <= mid) {
    152                 large[rs[o]] = largeD[rs[o]] = -INF;
    153                 del(p, l, mid, ls[o]);
    154             }
    155             else {
    156                 del(p, mid + 1, r, rs[o]);
    157             }
    158             pushup(o);
    159             return;
    160         }
    161     }
    162 
    163     void DFS_1(int x, int f) {
    164         for(int i = 0; i < (int)v[x].size(); i++) {
    165             int t = v[x][i];
    166             seg::insert(deep[node[t].w], node[t].val, d[node[t].w], d[x], 1, n, rt[x]);
    167         }
    168         forson(x, i) {
    169             int y = edge[i].v;
    170             if(y == f) continue;
    171             DFS_1(y, x);
    172             seg::del(deep[x], 1, n, rt[y]);
    173             rt[x] = seg::merge(rt[x], rt[y], d[x]);
    174         }
    175         return;
    176     }
    177 
    178     inline void solve() {
    179         seg::tot = 0;
    180         seg::large[0] = seg::largeD[0] = -INF;
    181         memset(rt + 1, 0, n * sizeof(int));
    182         for(int i = 1; i <= n; i++) v[i].clear();
    183 
    184         for(int i = 1; i <= m; i++) {
    185             int x = node[i].x, y = node[i].y, z = node[i].w;
    186             if(x != z) {
    187                 v[x].push_back(i);
    188             }
    189             if(y != z) {
    190                 v[y].push_back(i);
    191             }
    192         }
    193 
    194         DFS_1(1, 0);
    195         return;
    196     }
    197 }
    198 
    199 namespace Stwo { /// lca = 1
    200     Edge EDGE[N << 1]; int TP;
    201     int E[N], use[N], Time, cnt, imp[N], stk[N], top;
    202     std::vector<int> v[N], vx[N];
    203 
    204     inline void ADD(int x, int y) {
    205         TP++;
    206         EDGE[TP].v = y;
    207         EDGE[TP].nex = E[x];
    208         E[x] = TP;
    209         return;
    210     }
    211 
    212     inline void work(int x) {
    213         if(use[x] != Time) {
    214             use[x] = Time;
    215             E[x] = 0;
    216             v[x].clear();
    217             data[x].a = data[x].b = 0;
    218         }
    219         return;
    220     }
    221 
    222     inline void update(Data &x, const Data &y, const LL &v) {
    223         LL d12 = dis(x.a, x.b), d34 = dis(y.a, y.b);
    224         LL d13 = dis(x.a, y.a), d14 = dis(x.a, y.b);
    225         LL d23 = dis(x.b, y.a), d24 = dis(x.b, y.b);
    226         Ans = std::max(Ans, (std::max(std::max(d13, d14), std::max(d23, d24)) - v) >> 1);
    227         int xa = x.a, xb = x.b;
    228         if(d34 > d12) {
    229             x = y;
    230             d12 = d34;
    231         }
    232         if(d13 > d12) {
    233             x = Data(xa, y.a);
    234             d12 = d13;
    235         }
    236         if(d14 > d12) {
    237             x = Data(xa, y.b);
    238             d12 = d14;
    239         }
    240         if(d23 > d12) {
    241             x = Data(xb, y.a);
    242             d12 = d23;
    243         }
    244         if(d24 > d12) {
    245             x = Data(xb, y.b);
    246         }
    247         if(!x.a) x = y;
    248         return;
    249     }
    250 
    251     inline void update(Data &x, const int &a, const LL &v) {
    252         LL d1 = dis(x.a, a), d2 = dis(x.b, a), d3 = dis(x.a, x.b);
    253         Ans = std::max(Ans, (std::max(d1, d2) - v) >> 1);
    254         int xa = x.a, xb = x.b;
    255         if(d1 > d3) {
    256             x.b = a;
    257             d3 = d1;
    258         }
    259         if(d2 > d3) {
    260             x = Data(xb, a);
    261         }
    262         if(!x.a) x.a = a;
    263         return;
    264     }
    265 
    266     void dfs(int x, int f) {
    267         for(int i = E[x]; i; i = EDGE[i].nex) {
    268             int y = EDGE[i].v;
    269             if(y == f) continue;
    270             dfs(y, x);
    271             if(f) update(data[x], data[y], d[x] << 1);
    272         }
    273         if(f) {
    274             for(int i = 0; i < (int)v[x].size(); i++) {
    275                 int t = v[x][i];
    276                 update(data[x], t, d[x] << 1);
    277             }
    278         }
    279         return;
    280     }
    281 
    282     inline void build_t() {
    283         std::sort(imp + 1, imp + cnt + 1, cmp);
    284         cnt = std::unique(imp + 1, imp + cnt + 1) - imp - 1;
    285 
    286         stk[top = 1] = imp[1];
    287         for(int i = 2; i <= cnt; i++) {
    288             int x = imp[i], y = lca(x, stk[top]);
    289             work(x); work(y);
    290             while(top > 1 && pos2[y] <= pos2[stk[top - 1]]) {
    291                 ADD(stk[top - 1], stk[top]);
    292                 top--;
    293             }
    294             if(y != stk[top]) {
    295                 ADD(y, stk[top]);
    296                 stk[top] = y;
    297             }
    298             stk[++top] = x;
    299         }
    300         while(top > 1) {
    301             ADD(stk[top - 1], stk[top]);
    302             top--;
    303         }
    304         return;
    305     }
    306 
    307     inline void solve() {
    308 
    309         for(int i = 1; i <= n; i++) {
    310             vx[i].clear();
    311         }
    312 
    313         for(int i = 1; i <= m; i++) {
    314             vx[node[i].w].push_back(i);
    315         }
    316 
    317         for(int rt = 1; rt <= n; rt++) {
    318             if(!vx[rt].size()) continue;
    319             ++Time;
    320             TP = cnt = 0;
    321             work(rt);
    322             imp[++cnt] = rt;
    323             for(int j = 0; j < (int)vx[rt].size(); j++) {
    324                 int i = vx[rt][j];
    325                 int x = node[i].x, y = node[i].y, z = node[i].w;
    326                 work(x); work(y);
    327                 imp[++cnt] = x;
    328                 imp[++cnt] = y;
    329                 if(x != z) {
    330                     fr[n + i * 2 - 1] = y;
    331                     d[n + i * 2 - 1] = d[y] + d[x] + node[i].val - node[i].z;
    332                     v[x].push_back(n + i * 2 - 1);
    333                 }
    334                 if(y != z) {
    335                     fr[n + i * 2] = x;
    336                     d[n + i * 2] = d[x] + d[y] + node[i].val - node[i].z;
    337                     v[y].push_back(n + i * 2);
    338                 }
    339             }
    340             build_t();
    341             dfs(rt, 0);
    342         }
    343         return;
    344     }
    345 }
    346 
    347 inline void solve() {
    348     Ans = -INF;
    349     scanf("%d", &n);
    350     for(int i = 1; i <= n; i++) {
    351         fr[i] = i;
    352     }
    353     LL z;
    354     for(int i = 1, x, y; i < n; i++) {
    355         scanf("%d%d%lld", &x, &y, &z);
    356         add(x, y, z);
    357         add(y, x, z);
    358     }
    359 
    360     DFS(1, 0);
    361     prework();
    362 
    363     scanf("%d", &m);
    364     for(int i = 1, x, y; i <= m; i++) {
    365         scanf("%d%d%lld", &x, &y, &z);
    366         node[i].x = x;
    367         node[i].y = y;
    368         node[i].z = z;
    369         node[i].val = dis(x, y) - z;
    370         node[i].w = lca(x, y);
    371     }
    372 
    373     Sone::solve();
    374     Stwo::solve();
    375 
    376     if(Ans < (LL)-1e18) puts("F");
    377     else printf("%lld\n", Ans);
    378     return;
    379 }
    380 
    381 int main() {
    382 
    383     for(int i = 2; i < N; i++) pw[i] = pw[i >> 1] + 1;
    384 
    385     int T;
    386     scanf("%d", &T);
    387     while(T--) {
    388         solve();
    389         if(T) clear();
    390     }
    391     return 0;
    392 }

AC代码

这什么鬼题啊...搞了4天，结果写完啥都没学到......

转载于:https://www.cnblogs.com/huyufeifei/p/10679339.html

[1332167-20190409200650468-2013514623.png]: /images/20211220/db0a88e666da4a378313c80b4368726f.png
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211220/a49ca2be8878483f88efb62025993afb.png
[1332167-20190411164604840-2077384845.png]: /images/20211220/0a5eedaeb4684c7fafdf030fafdd3067.png
[1332167-20190412105002710-1709940313.png]: /images/20211220/26d2d47f21e54dd497a09f241771c927.png
[1332167-20190412194837597-1423067144.png]: /images/20211220/0cb81168f923495d90cd39c6f985dd7c.png
[1332167-20190412195722884-1286743983.png]: /images/20211220/c28b257eaa494e7cabcab2dcc259b776.png