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}\) 是边权。
标签:sz,环上,Union,times,fa,CF48G,Galaxy From: https://www.cnblogs.com/zhouzizhe/p/16909236.html