题意：给定两棵树T1，T2，求d1[x] + d1[y] - d1[lca1(x, y)] - d2[lca2(x, y)]的最大值。
解：考虑把上面这个毒瘤东西化一下。发现它就是T1中x，y到根的路径并 - T2中x，y到根的路径交。
也就是T1中的一个三叉状路径和T2中lca到根的路径。
根据情报中心的套路，把这个东西 * 2，发现就是d1[x] + d1[y] + dis1(x, y) - d2[x] - d2[y] + dis2(x, y)
令val[i] = d1[i] - d2[i]，我们就要令val[x] + val[y] + dis1(x, y) + dis2(x, y)最大。
考虑在T1上边分治，这样的话dis1(x, y) = d[x] + d[y] + e。e是分治边的长度。
在T2上把T1这次分治的点全部提出来建虚树。我们不妨把每个T1的节点挂到对应的虚树节点上，边权为val[x] + d[x]，那么我们就是要在虚树上挂的点中找到两个异色节点，使得它们距离最远。
此时我们有一个非常优秀的O(n)DFS算法......但是我就是SB中的SB中的SB，把这个问题搞成了nlogn。这个解决之后本题就做完了。为了卡常用了优秀的zkw线段树。
1 #include2 3 #define forson(x, i) for(register int i = e[x]; i; i = edge[i].nex) 4 5 #define add(x, y, z) edge[++tp].v = y; edge[tp].len = z; edge[tp].nex = e[x]; e[x] = tp 6 #define ADD(x, y) EDGE[++TP].v = y; EDGE[TP].nex = E[x]; E[x] = TP 7 8 typedef long long LL; 9 const int N = 800010; 10 const LL INF = 4e18; 11 12 inline char gc() { 13 static char buf[N], *p1(buf), *p2(buf); 14 if(p1 == p2) p2 = (p1 = buf) + fread(buf, 1, N, stdin); 15 return p1 == p2 ? EOF : *p1++; 16 } 17 18 template inline void read(T &x) { 19 x = 0; 20 register char c(gc()); 21 bool f(false); 22 while(c < '0' || c > '9') { 23 if(c == '-') f = true; 24 c = gc(); 25 } 26 while(c >= '0' && c <= '9') { 27 x = x * 10 + c - 48; 28 c = gc(); 29 } 30 if(f) x = (~x) + 1; 31 return; 32 } 33 34 struct Edge { 35 int nex, v; 36 bool vis; 37 LL len; 38 }edge[N << 1], EDGE[N << 1]; int tp = 1, TP; 39 40 int pw[N << 1], n, e[N], Cnt, _n, small, root, imp[N], K, use[N], Time, stk[N], top, E[N], RT, POS[N], NUM, SIZ[N], ID[N], vis[N], siz[N]; 41 LL val[N], ans = -INF, d[N], VAL[N], H[N], C[N], W[N]; 42 std::vector G[N]; 43 std::vector Len[N]; 44 45 namespace seg2 { 46 LL large[N << 2]; 47 void build(int l, int r, int o) { 48 if(l == r) { 49 large[o] = VAL[ID[r]]; 50 //if(F) printf("p = %d x = %d val = %lld \n", r, ID[r], VAL[ID[r]]); 51 return; 52 } 53 int mid((l + r) >> 1); 54 build(l, mid, o << 1); 55 build(mid + 1, r, o << 1 | 1); 56 large[o] = std::max(large[o << 1], large[o << 1 | 1]); 57 return; 58 } 59 LL getMax(int L, int R, int l, int r, int o) { 60 if(L <= l && r <= R) { 61 return large[o]; 62 } 63 LL ans = -INF; 64 int mid((l + r) >> 1); 65 if(L <= mid) ans = getMax(L, R, l, mid, o << 1); 66 if(mid < R) ans = std::max(ans, getMax(L, R, mid + 1, r, o << 1 | 1)); 67 return ans; 68 } 69 } 70 71 namespace seg { 72 LL large[N << 2]; 73 int lm; 74 inline void build(int n) { 75 lm = 1; n += 2; 76 while(lm < n) lm <<= 1; 77 large[lm] = -INF; 78 for(register int i = 1; i <= n; i++) { 79 large[i + lm] = VAL[ID[i]]; 80 } 81 for(register int i = n + 1; i < lm; i++) { 82 large[i + lm] = -INF; 83 } 84 for(int i = lm - 1; i >= 1; i--) { 85 large[i] = std::max(large[i << 1], large[i << 1 | 1]); 86 } 87 return; 88 } 89 inline LL getMax(int L, int R) { 90 LL ans = -INF; 91 for(int s = lm + L - 1, t = lm + R + 1; s ^ t ^ 1; s >>= 1, t >>= 1) { 92 if(t & 1) { 93 ans = std::max(ans, large[t ^ 1]); 94 } 95 if((s & 1) == 0) { 96 ans = std::max(ans, large[s ^ 1]); 97 } 98 } 99 return ans;100 }101 }102 103 namespace t1 {104 int e[N], pos2[N], ST[N << 1][20], num2, deep[N];105 LL d[N];106 Edge edge[N << 1]; int tp;107 void DFS_1(int x, int f) {108 deep[x] = deep[f] + 1;109 pos2[x] = ++num2;110 ST[num2][0] = x;111 forson(x, i) {112 int y(edge[i].v);113 if(y == f) continue;114 d[y] = d[x] + edge[i].len;115 DFS_1(y, x);116 ST[++num2][0] = x;117 }118 return;119 }120 inline void prework() {121 for(register int j(1); j <= pw[num2]; j++) {122 for(register int i(1); i + (1 << j) - 1 <= num2; i++) {123 if(deep[ST[i][j - 1]] < deep[ST[i + (1 << (j - 1))][j - 1]]) {124 ST[i][j] = ST[i][j - 1];125 }126 else {127 ST[i][j] = ST[i + (1 << (j - 1))][j - 1];128 }129 }130 }131 return;132 }133 inline int lca(int x, int y) {134 x = pos2[x], y = pos2[y];135 if(x > y) std::swap(x, y);136 int t(pw[y - x + 1]);137 if(deep[ST[x][t]] < deep[ST[y - (1 << t) + 1][t]]) {138 return ST[x][t];139 }140 else {141 return ST[y - (1 << t) + 1][t];142 }143 }144 inline LL dis(int x, int y) {145 return d[x] + d[y] - 2 * d[lca(x, y)];146 }147 }148 149 void rebuild(int x, int f) {150 int temp(0);151 for(register int i(0); i < G[x].size(); i++) {152 int y = G[x][i];153 LL len = Len[x][i];154 if(y == f) continue;155 if(!temp) {156 add(x, y, len);157 add(y, x, len);158 temp = x;159 }160 else if(i == G[x].size() - 1) {161 add(temp, y, len);162 add(y, temp, len);163 }164 else {165 add(temp, ++Cnt, 0);166 add(Cnt, temp, 0);167 temp = Cnt;168 add(temp, y, len);169 add(y, temp, len);170 }171 d[y] = d[x] + len;172 rebuild(y, x);173 }174 return;175 }176 177 void getroot(int x, int f) {178 siz[x] = 1;179 //printf("getroot : x = %d \n", x);180 forson(x, i) {181 int y(edge[i].v);182 if(y == f || edge[i].vis) continue;183 getroot(y, x);184 if(small > std::max(siz[y], _n - siz[y])) {185 small = std::max(siz[y], _n - siz[y]);186 root = i;187 }188 siz[x] += siz[y];189 }190 //printf("siz %d = %d \n", x, siz[x]);191 return;192 }193 194 void DFS_1(int x, int f, int flag) {195 siz[x] = 1;196 //printf("x = %d d = %lld \n", x, d[x]);197 if(!flag && x <= n) {198 imp[++K] = x;199 vis[x] = Time;200 //if(F) printf("vis %d = Time \n", x);201 }202 else if(flag && x <= n) {203 imp[++K] = x;204 }205 forson(x, i) {206 int y(edge[i].v);207 if(y == f || edge[i].vis) continue;208 d[y] = d[x] + edge[i].len;209 DFS_1(y, x, flag);210 siz[x] += siz[y];211 }212 return;213 }214 215 inline void work(int x) {216 if(use[x] == Time) return;217 use[x] = Time;218 E[x] = 0;219 return;220 }221 222 inline bool cmp(const int &a, const int &b) {223 return t1::pos2[a] < t1::pos2[b];224 }225 226 inline void build_t() {227 std::sort(imp + 1, imp + K + 1, cmp);228 K = std::unique(imp + 1, imp + K + 1) - imp - 1;229 work(imp[1]);230 stk[top = 1] = imp[1];231 for(register int i(2); i <= K; i++) {232 int x = imp[i], y = t1::lca(x, stk[top]);233 work(x); work(y);234 while(top > 1 && t1::pos2[y] <= t1::pos2[stk[top - 1]]) {235 ADD(stk[top - 1], stk[top]);236 top--;237 }238 if(y != stk[top]) {239 ADD(y, stk[top]);240 stk[top] = y;241 }242 stk[++top] = x;243 }244 while(top > 1) {245 ADD(stk[top - 1], stk[top]);246 top--;247 }248 RT = stk[top];249 return;250 }251 252 void dfs_2(int x) {253 //printf("dfs_2 x = %d \n", x);254 SIZ[x] = 1;255 POS[x] = ++NUM;256 ID[NUM] = x;257 if(vis[x] == Time) VAL[x] = t1::d[x] + val[x] + d[x];258 else VAL[x] = -INF;259 /*if(F && x == 3) {260 printf("VAL 3 = %lld + %lld + %lld \n", t1.d[x], val[x], d[x]);261 }*/262 C[x] = VAL[x];263 for(register int i(E[x]); i; i = EDGE[i].nex) {264 int y = EDGE[i].v;265 dfs_2(y);266 SIZ[x] += SIZ[y];267 C[x] = std::max(C[x], C[y]);268 }269 //if(F) printf("x = %d VAL = %lld C = %lld \n", x, VAL[x], C[x]);270 return;271 }272 273 void dfs_3(int x, int f) {274 if(f) {275 /// cal H[x]276 H[x] = seg::getMax(POS[f], POS[x] - 1);277 if(POS[x] + SIZ[x] < POS[f] + SIZ[f]) {278 H[x] = std::max(H[x], seg::getMax(POS[x] + SIZ[x], POS[f] + SIZ[f] - 1));279 }280 W[x] = std::max(W[f], H[x] - 2 * t1::d[f]);281 }282 else {283 H[x] = W[x] = -INF;284 }285 //if(F) printf("x = %d H = %lld W = %lld \n", x, H[x], W[x]);286 for(register int i(E[x]); i; i = EDGE[i].nex) {287 int y(EDGE[i].v);288 dfs_3(y, x);289 }290 return;291 }292 293 void DFS_4(int x, int f, LL v) {294 /// ask295 if(x <= n) {296 VAL[x] = t1::d[x] + val[x] + d[x] + v;297 ans = std::max(ans, VAL[x] + W[x]);298 ans = std::max(ans, VAL[x] + C[x] - 2 * t1::d[x]);299 }300 forson(x, i) {301 int y(edge[i].v);302 if(y == f || edge[i].vis) continue;303 DFS_4(y, x, v);304 }305 return;306 }307 308 void e_div(int x) {309 if(_n == 1) {310 ans = std::max(ans, val[x] << 1);311 return;312 }313 small = N;314 getroot(x, 0);315 edge[root].vis = edge[root ^ 1].vis = 1;316 317 x = edge[root].v;318 int y = edge[root ^ 1].v;319 if(siz[x] < _n - siz[x]) std::swap(x, y);320 321 //if(F) printf("div %d %d _n = %d \n", x, y, _n);322 323 ///324 d[x] = d[y] = 0;325 TP = K = 0;326 Time++;327 DFS_1(x, 0, 0);328 DFS_1(y, 0, 1);329 /// build virtue trEE330 build_t();331 //printf("v_t build over \n");332 /// prework333 NUM = 0;334 dfs_2(RT);335 //printf("dfs_2 over \n");336 seg::build(NUM);337 //printf("seg build over \n");338 dfs_3(RT, 0);339 DFS_4(y, 0, edge[root].len);340 341 //if(F) printf("ans = %d \n", ans);342 343 _n = siz[x];344 e_div(x);345 _n = siz[y];346 e_div(y);347 return;348 }349 350 int main() {351 352 W[0] = -INF;353 read(n);354 LL z;355 for(register int i(1), x, y; i < n; i++) {356 read(x); read(y); read(z);357 G[x].push_back(y);358 G[y].push_back(x);359 Len[x].push_back(z);360 Len[y].push_back(z);361 }362 for(register int i(1), x, y; i < n; i++) {363 read(x); read(y); read(z);364 t1::edge[++t1::tp].v = y;365 t1::edge[t1::tp].len = z;366 t1::edge[t1::tp].nex = t1::e[x];367 t1::e[x] = t1::tp;368 t1::edge[++t1::tp].v = x;369 t1::edge[t1::tp].len = z;370 t1::edge[t1::tp].nex = t1::e[y];371 t1::e[y] = t1::tp;372 }373 for(register int i = 2; i <= n * 2; i++) {374 pw[i] = pw[i >> 1] + 1;375 }376 t1::DFS_1(1, 0);377 t1::prework();378 379 Cnt = n;380 rebuild(1, 0);381 for(register int i(1); i <= n; i++) {382 val[i] = d[i] - t1::d[i];383 }384 /// ans = val[i] + val[j] + t0.dis(i, j) + t1.dis(i, j);385 _n = Cnt;386 e_div(1);387 388 printf("%lld\n", ans >> 1);389 return 0;390 }
讲一下我的做法。考虑到两个点的距离是d + d - 2 * lca，我们预处理某一颜色的节点，然后枚举另一个颜色的所有点。
由于开店的启发，我们可以把每个点往上更新链，然后每个点往上查询链。
进而发现，查询全是静态的，所以可以预处理出一个点到根路径上的max，变成单点查询。
设VAl[x]为挂上的节点x的深度。C[x]为x的子树中的最大VAL值。
设H[x]为（subtree(fa[x]) \ subtree(x)的最大VAL值） - 2 * VAL[x]，W[x]为x到根路径上的最大H值。
那么对于一个点x，它只要和W[x]，C[x] - 2 * VAL[x]拼起来就能得到跟它相关的最远点对距离了。
复杂度在于求H[x]的时候使用DFS序 + RMQ，写了一个log。所以总复杂度是nlog2n。
有个T1是链且v > 0的部分分。这里我们发现T1的路径并变成了max(d1[x], d1[y])，于是考虑枚举T2中每个点作为lca，要求两个点在其子树中，且max(d1[x], d1[y])最大。显然维护一个子树最大值就好了。实测有80分呢......
还有个迭代乱搞是随机选一个起点，每次迭代找到一个点与之贡献最大并更新那个点为新的起点。多来几次。这样也有80分呢......
比写正解不知道高到哪里去了...