P4220 [WC2018]通道

eee_hoho

2021-03-10 11:34:27

Solution

谁说边分治能干的点分治干不了?我点分治一样过好吧。 先考虑边分治的做法,我们对第一棵树边分治,每次得到两个联通块的时候,对联通块黑白染色,考虑不同联通块跨越中心边的贡献。 设中心边端点是 $x,y$ ,对于颜色不同的两个点 $u,v$ ,我们有 $dis_1(u,x)+w(x,y)+dis_1(y,v)+dep_2(u)+dep_2(v)+2dep_2(lca(u,v))+dep_3(u)+dep_3(v)+2dep_3(lca(u,v))$ ,其中 $dep_x$ 是 $x$ 到根的权值和,$w$ 是常数,我们先拿掉,然后考虑对第二棵树建虚树,枚举 $lca$ ,对于第三棵树,我们可以用dp来求出最值。 假设现在在第二棵树上枚举到了点 $p$ ,那么 $p$ 不同子树的 $lca$ 就是 $p$ ,我们在第三棵树上每个点 $u$ 连向一个虚点,边权为 $dis(u)=dis_1(u,x)+dep_2(u)$ ,考虑在第三棵树上维护直径,维护出来颜色不同的两个点集的直径 $f_{u,0/1}$ ,然后用不同颜色的 $f$ 来更新答案,也就是 $max(f_{p,0}+f_{v,1},f_{p,1}+f_{v,0})+w(x,y)-2dep_3(lca(u,p))$ ,这里 $f$ 的加法是合并直径。 复杂度 $O(n\log^2 n)$ 。 这题之所以用边分治是因为我们每次要合并两个联通块,而点分治没法每次只分出来两个联通块。 那么我们就规定一个合并联通块的顺序,来保证复杂度。 考虑使用合并果子的方法,每次只合并两个点数最小的联通块,如果每次合并和计算的复杂度都是 $O(size_x+size_y)$ ,那么复杂度仍然是 $O(n\log n)$ 。 证明的话,我们对合并过程建哈夫曼树,一个点数为 $s$ 的联通块在哈夫曼树的深度是 $\log \frac{n}{s}$ ,那么我们写出来复杂度: $$\begin{aligned}T(u)&=\sum_{v\in son(u)}size_v\log n-\sum_{v\in son(u)}size_v\log size_v+\sum_{v\in son(u)}T(v)\\&=size_u\log n-\sum_{v\in son(u)}size_v\log size_v+\sum_{v\in son(u)}T(v)\end{aligned}$$ 我们会发现这样迭代下去中间的一项会两两减掉,那么就只剩了 $T(n)=\sum_{v\in son(u)}size_v\log n=n\log n$ 。 由于我写的代码又丑又长,所以我就放剪贴板了。 [边分治](https://www.luogu.com.cn/paste/e2ma45ii) [点分治](https://www.luogu.com.cn/paste/y6olhpl8)