BZOJ 2888 资源运输

发布于 2017-11-24  160 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2888

题意:动态加边维护树重心,查询每个点到重心距离和。


加边操作用 lct 维护即可,重心怎么维护呢。

考虑更简单的,加入一个点,这样的话重心要么往这个点的方向走一步,要么不变,维护一下 size 即可判断。

所以合并树的时候将较小的那个拆开一个个加入,启发式合并,复杂度\(O(nlog_{n}^2)\)

发现维护 size 是子树信息,统计答案的子树内点到根的距离和也是子树信息,不会写 lct 维护子树信息,怎么办?

发现修改操作只修改到根一条链是 size+1,直接打标记即可,对答案的贡献是从叶到根的一条链加等差数列,维护首项和公比即可。

 


一个非常弱的准退役OIER