CF48G Galaxy Union

给定一棵基环树，求每个点到其他点的最小距离之和。 \(n\leq 2\times 10^5\) 。

对于在环上的点和在树上的点分开处理。设在环上的点集为 \(H\) ，先求出所有在环上的点 \(i\) 到其他点在环上的距离之和 \(ans_i=\sum\limits_{j\in H} dis(i,j)\times sz_j\) ，其中 \(sz_j\) 表示 \(j\) 的树部分大小，可以做到使用双指针断环为链 \(O(n)\) 求出（因为每个点都可以贪心取较小的一半距离）。

然后所有树上的节点 \(p\) 在环上的答案贡献就是 \(ans_i+\sum\limits_{j\in H\&j\neq i}sz_j\times dis(i,p)\) 。

最后要求树内节点的答案，发现就是当以自己为根是的 \(dep\) 之和，于是可以套上一个简单的换根 DP 解决，式子是 \(f_x=f_{fa}-2\times sz_x\times w_{x,fa}+sz_{root}\times w_{x,fa}\) ，其中 \(sz_x\) 为原树内的子树大小， \(root\) 是所属的子树在链上的点， \(w_{x,fa}\) 是边权。

原文地址：http://www.cnblogs.com/zhouzizhe/p/16909236.html