通道 WC2018

[WC2018] 通道

genlib 真是太好用了。

题目链接： [WC2018] 通道 。

题目描述：

给你三棵树 $T_1,T_2,T_3$ 。

求 $\max\limits_{a,b}\{dist_1(a,b)+dist_2(a,b)+dist_3(a,b)\}$ 。

$n\le 10^5$ 。

这一看就是一个类似树的直径的东西。于是考虑边分治。在 $T_1$ 上边分治后会得到左右两个点集，不妨记为 $A,B$ 。设这些点到其中一个中心边的端点的距离为 $val_a$ ，那么就有 $dist_1(a,b)=val_a+val_b$ ，其中 $a\in A,b\in B$ 。

此时式子变为最大化 $val_a+val_b+dist_2(a,b)+dist_3(a,b)$ ，此时可以在 $T_2$ 上继续边分治，然后在 $T_3$ 上建立虚树，获得 $O(n\log^2n)$ 的复杂度以及 $O(\infty)$ 的常数，不可取。所以只能将 $A,B$ 点集中的点在 $T_2$ 中建立虚树。设某一点 $a$ 到虚树根节点的距离为 $d_a$ ，那么就有 $dist_2(a,b)=d_a+d_b-2d_{lca(a,b)}$ 。

然后，自然的，在虚树上枚举他们的 $lca$ ，设为 $L$ ，那么式子变为最大化 $(val_a+d_a)+(val_b+d_b)+dist_3(a,b)-2d_L$ 。其中 $d_L$ 是常数，可以忽略。那么剩下的就是一个类似于带权树的直径的东西。这个东西可以通过对于 $T_3$ 的每个节点 $i$ ，新建一条边连向 $i$ 和虚节点 $i+n$ ，边权为 $val_i+d_i$ ，然后就变成了最大化 $dist'_3(a,b)$ ，这是一个标准的树的直径问题。但是有 $a\in A,b\in B$ 的限制，我们必须在 $O(1)$ 或 $O(\log n)$ 的复杂度内解决。

由于边带正权，那么有如下定理：

对于点集 $A,B$ ，树上 $A\cup B$ 的直径的端点必然是 $A$ 直径的端点和 $B$ 直径的端点中的两个。

那么只需要合并儿子贡献就行了。

特别的，统计答案应该在合并儿子贡献时统计，不然无法保证 $lca$ 为 $L$ 。合并儿子需要枚举 $6$ 种情况，统计答案要枚举 $8$ 种情况，都枚举到就行了。

代码写了 $6KB$ ，不放了。