P6329 【模板】点分树 | 震波

来补点分树模板的题解了：

先明确一下点分树的定义：又很多个重心构成的一棵树，且树上的层数关系对应重心的大小

那么我们为什么要建这一颗树呢：因为我们要处理多组询问并且又修改.

然后点分树的建树方式其实在定义中就几乎给出了，就是在求重心时将新老重心连一条边.

然后我们开始思考本题：“所有与 x 距离不超过 k 的城市都将受到影响”:
我们不难想到对于一个重心lca，在它的子树下对答案的贡献(将目标节点设为y)就是:

\(\sum{y\in S_{lca}}[dis_{y,lca}\le k-dis_{lca,x}]*val_y -\sum{y\in S_{ancx}}[dis_{y,lca}\le k-dis_{lca,x}]*val_y\)

其中，\(S_{lca}\)表示在lca的子树内,\(S_{ancx}\)类似.
节点ancx表示的是一个既是lca的儿子，又是x的先祖(也可能是本身)的节点.

然后这题的思路就比较明确了:维护两颗动态开点线段树，对于一个点x:
T1维护\(sum_y|\) \(\forall y \in S_{x}\) $ dis_{x,y}\in[l,r]$
T2维护\(sum_y|\) \(\forall y \in S_{x}\) $ dis_{fa,y}\in[l,r]$
其中fa为x在点分树上的父亲

然后对于每个操作，在点分树上不断向上跳并执行对应操作就好了

然后这题就愉快的做完了

我是绝对不会告诉你我卡了一下午常的