BZOJ4012(LOJ2116) [HNOI2015]开店

题目链接

题目链接2

 

Solution

强制在线,动态点分治。

由于是计算距离和,贡献不能叠加。

考虑消除对父亲的影响,直接记子树中所有点到父亲的距离和,算答案的时候减掉即可。

 

Hints

跑的太慢了。。。

听说有一个的做法。

咕咕咕。。。

 

Code