题解 P4220 【[WC2018]通道】

immortalCO · 2018-02-10 20:30:44 · 题解

对 T_1 进行边分治。每次分治的时候，考虑跨越中心边的两个所有路径。中心边将当前连通块分为左右两个连通块 L 和 R。设点 i 到中心边的距离为 d_1(i)，那么我们就是要找一对 i\in L,j\in R，使得 d_1(i) + d_1(j) + dist_{T_2}(i,j) + dist_{T_3}(i, j) 最大。

建立 L\cup R 的关于 T_2 的虚树 T_2^{'}，在虚树上进行 DFS。设点 i 在 T_2 上的带权深度为 d_2(i)。在虚树上 DFS 到 p 的时候，考虑所有在 T_2^{'} 中的 LCA 为 p、且 i\in L,j\in R 点对 (i,j)，求出 d_1(i) + d_2(i) + d_1(j) + d_2(j) + dist_{T_3}(i,j) - 2d_2(p) 最大。其中最后一项和 i,j 无关，可以省略。前三项可以看作是 (d_1+d_2)(i) + (d_1+d_2)(j) + dist_{T_3}(i, j)，即可以认为是在 T_3 中，对每个点 i 新建一个点 i_{'}，和 i 连接边权为 d_1(i) + d_2(i) 的边，求这棵树（称作 T_3^{'}）中的满足 L 和 R 包含条件的最长路径。

由于边权非负，性质“集合合并后最长路的端点一定是两个集合各自的最长路端点中的两个点”成立，因此使用并查集来维护。记 f_{L/R}(i) 表示 (i,j) 都在 [T_2^{'} 的 i 的子树的点集交上 L/R] 这个点集中时，在 T_3^{'} 中的最长路的两个端点，那么 f_{L/R} 容易转移。同时由于边权非负，要求出一个端点在集合 A 中、另一个在集合 B 中的最长路，这条最长路的端点一定一个是 A 的最长路的其中一个端点，另一个是 B 的最长路的其中一个端点，因此就可以在 i 和其子节点 j 转移的时候，用 f_{L}(i) 和 f_{R}(j) 组合更新答案，再用 f_{R}(i) 和 f_{L}(j) 组合更新答案（注意在这里更新答案的时候要减去 2d_2(i)）。

这样这题就做完了。直接实现的话 O(n\log^2n)，因为要求虚树和距离。如果强行优化的话可以优化成 O(n\log n)（LCA 可以用 O(n\log n) 预处理 O(1) 回答，虚树可以离线然后使用基数排序）。