边分治神题。
前置知识：边分治，虚树。
题意
给定 $3$ 棵有边权的树，每棵树都含有 $n$ 个节点，令 $dis_i(x, y)$ 表示 $(x, y)$ 在第 $i$ 棵树上的距离。求一组 $(i, j)$，使得 $\sum\limits_{k = 1}^3 dis_k(i, j)$ 最大，为了方便，只需输出最大值。
题解
考虑边分治。下面用 \(T_i\) 来表示第 \(i\) 棵树。
对 \(T_1\) 进行边分治，设 \(d_1(x)\) 表示 \(x\) 点到分治边一侧的距离，那么答案就转化成了 \(d_1(i) + d_1(j) + dis_2(i, j) + dis_3(i, j)\)。然后将当前分治块内的所有点在 \(T_2\) 上拉出来，建一棵虚树 \(T'_2\)，再设 \(d_2(x)\) 表示 \(x\) 在 \(T_2\) 上的带权深度，答案又转化成了 \(d_1(i) + d_1(j) + d_2(i) + d_2(j) + dis_3(i, j) - 2d_2{p}\)，其中 \(p\) 表示 \(T'_2\) 中 \((i, j)\) 的 \(\text{LCA}\)，显然 \(p\) 也是 \(T_2\) 中 \((i, j)\) 的 \(\text{LCA}\)。
所以现在枚举 \(p\)，然后在 \(p\) 在 \(T'_2\) 的子树中，找到 \((i, j)\) 使：1. \(i, j\) 在 \(T_1\) 的分治边的两侧。2. 答案最大。接着可以发现，上面的答案可以变成 \((d_1 + d_2)(i) + (d_1 + d_2)(j) + dis_3(i, j) - 2d_2(p)\)，因为 \(p\) 是我们枚举的，故可以省略。接着，考虑把 \((d_1 + d_2)(i) + (d_1 + d_2)(j)\) 给转化一下。一个精妙的处理方法是：在 \(T_3\) 中新建 \(i', j'\)，然后将 \(i'\) 与 \(i\) 之间连一条边权为 \(d_1(i) + d_2(i)\) 的边，对 \(j\) 和 \(j'\) 同理。这样答案就转化成了 \(dis_3(i', j') - 2d_2(p)\)，也就是求 \(T_3\) 中的最长路（要保证 \(i, j\) 在分治边的两侧）。
我们发现，最长路竟然是可以合并的！也就是说：设 \(x\) 只有两个儿子，\(l, r\) 是 \(x\) 的左儿子子树的最长路两端点，\(l', r'\) 是右儿子的。那么 \(x\) 的最长路两端点一定是 \(l, l', r, r'\) 中的两个！根据这个结论，就可以在 \(T'_2\) 上面进行合并了。有一个细节，设 \(L\) 表示分治边左侧的点集，\(R\) 表示分治边右侧的点集，如果要保证 \((i, j)\) 在分治边的两侧，那么先把 \(L\) 的最长路和 \(R\) 的最长路分别求出，然后再对两个最长路，分别选出一个点进行合并，这才能保证 \(i, j\) 在不同侧的限制。
于是这题就做完了，时间复杂度 \(O(n \log^2 n)\)。代码可能有点难写。
标签：表示,分治,P4220,笔记,2d,答案,通道,最长,dis From： https://www.cnblogs.com/CTHOOH/p/17997067