总结点分树（动态点分治）

点分治是不支持修改的，所以根据点分治的过程，建出一个新的树形结构，具有许多很好的性质。

基本思想

回忆点分治，每次找重心，划分成若干个连通块递归处理。

如果将每个点为重心时，以上一层的重心为父亲，就能提出一个新树。

根据点分治的复杂度，这棵树树高明显是 \(\log n\) 的。

并且可以证明，这棵树所有子树的节点数之和约为 \(n\log n\)（每个点最多有 \(\log n\) 个祖先）。

其实就是把点分治抽象的过程具体化了，树上的每个点也就代表以它为根的子树形成的连通块，所以可以在该点用一些带修数据结构维护这个连通块的信息。

int n, root, all;
int size[N], fa[N], maxs[N];
void get_root(int u, int pre) {
    size[u] = 1, maxs[u] = 0;
    for (int i = G.head[u]; i; i = G.nxt[i]) {
        int v = G.to[i];
        if (vis[v] || v == pre) continue;
        get_root(v, u);
        size[u] += size[v];
        maxs[u] = max(maxs[u], size[v]);
    }
    maxs[u] = max(maxs[u], all - size[u]);
    if (!root || maxs[u] < maxs[root]) root = u;
}

void build(int u, int fat) {
    fa[u] = fat;
    vis[u] = true;
    int now = all;
    for (int i = G.head[u]; i; i = G.nxt[i]) {
        int v = G.to[i];
        if (vis[v]) continue;
        all = size[v] > size[u] ? (now - size[u]) : size[v];
        root = 0;
        get_root(v, u);
        build(root, u);
    }
}

// main
all = n, root = 0, get_root(1, 0), build(root, 0);

例题

P6329 【模板】点分树 | 震波

每次单点修改、询问距离点 \(x\) 距离 \(\le k\) 的点权值和。

\(n,m\le 10^5\)。

设 \(dis(u,v)\) 表示在原树上 \(u,v\) 两点的距离，\(fa_u\) 表示点分树上 \(u\) 的父亲。

类似点分治的容斥，点分树上每个点可以维护两棵树状数组：

\(f_1(u,i)\) 表示在点分树上以 \(u\) 根的子树中 \(dis(u,v)\le i\) 的点 \(v\) 的权值和；

\(f_2(u,i)\) 表示在点分树上以 \(u\) 根的子树中 \(dis(fa_u,v)\le i\) 的点 \(v\) 的权值和；

这样每次查询点 \(x\) 时，在点分树上 \(u\) 从 \(x\) 往上跳，每层的贡献就是：

\[ f_1(fa_u,k-dis(fa_u,x))-f_2(u,k-dis(fa_u,x)) \]

修改同理。

但是每个点开一棵树状数组爆空间？根据重心的性质，大小为 \(s\) 的连通块中每个点与重心的距离不超过 \(\frac{s}{2}\)，\(f_1\) 中 \(i\) 的范围 \([0,\frac{s}{2}]\)，\(f_2\) 中 \(i\) 的范围 \([1,s]\)，可以每个点用 vector，空间复杂度 \(\mathcal O(n\log n)\)。

求 \(dis\) 可以用重链剖分在线 \(\mathcal O(\log n)\) 求，所以总复杂度 \(\mathcal O(n\log^2 n)\)。

code

一些题目

点分树常用容斥的套路，在点分树上，

设 \(f_1(x)\) 表示以 \(x\) 为根的子树里的点对 \(x\) 的贡献；

设 \(f_2(x)\) 表示以 \(x\) 为根的子树对 \(f_1(fa_x)\) 的贡献。

下文可能会省略定义。

P3241 [HNOI2015]开店

题目

每个点有点权 \(A_i\)，每次给出 \(x,l,r\)，询问 \(\sum_{l\le Ay\le r}dis(x,y)\)。

\(n\le 1.5\times 10^5\)，\(Q\le 2\times 10^5\)。

答案差分一下，每次询问 \(\le k\) 的答案。

设 \(s(u,i)\) 表示点分树上以 \(u\) 为根的子树中 \(A_v\le k\) 的 \(v\) 个数。

每一层的答案为 \(f_1(fa_u,k)-f_2(u,k)+dis(x,fa_u)\times(s(fa_u,k)-s(u,k))\)。

怎么求 \(f_1(fa_u,k)\)？发现 \(A_i\) 值域 \(10^9\)，但是没有修改，那就每个点维护一个 vector，按 \(A_i\) 排序并前缀和，每次二分即可。

时间复杂度 \(\mathcal O((n+Q)\log^2n)\)。

code

P3345 [ZJOI2015]幻想乡战略游戏

题目

设 \(F(u)=\sum_v dis(u,v)\times val_v\)，每次修改点权后查询 \(F\) 值最小的点。

\(n,Q\le 10^5\)，每个点度数 \(\le 20\)。

设 \(S(x)\) 表示以 \(x\) 为根的子树点权和。

先设 \(x\) 为树根，得到 \(F(x)\)，若将根转移到 \(x\) 的儿子 \(y\)，则 \[ \begin{aligned} \Delta F_{x\rightarrow y}&=F(y)-F(x)\\ &=(S(x)-S(y))\times dis(x,y)-S(y)\times dis(x,y)\\ &= (S(x)-2S(y))\times dis(x,y) \end{aligned} \] 若让 \(\Delta F_{x\rightarrow y}<0\)，则 \(2S(y)>S(x)\)，\(x\) 的儿子中满足的 \(y\) 至多有一个。

暴力思路：在原树上，从根开始，不断跳到到更优的儿子，单次复杂度 \(\mathcal O(20\cdot depth)\)，\(depth\) 为树高。

不过辰星凌的博客告诉我们，还需要证明若某一步 \(y\) 不比 \(x\) 优则 \(y\) 的子树中也没有比 \(x\) 优的节点。

证明：若 \(y\) 再转移到 \(y'\) \[ \Delta F_{y\rightarrow y'}=(S(x)-2S(y'))\times dis(y,y') \] 若 \(\Delta F_{x\rightarrow y}>0\)，\(S(x)> 2S(y)\)，又因为 \(S(y)\ge S(y')\)，所以 \(S(x)> 2S(y')\)，

即 \(\Delta F_{y\rightarrow y'}>0,\Delta F_{x\rightarrow y'}>0\)。

如何控制树高？放到点分树上。

从重心 \(x\) 开始，在原树上找到更优的儿子 \(y\)，但是要跳到以 \(y\) 为根的子树的重心上，毕竟答案一定在这棵子树里。

如何计算某个点的 \(F\) 值？

还是点分树上跳 \(fa\)，每一层的答案是 \(f_1(fa_u)-f_2(u)+(s(fa_u)-s(u))\times dis(x,fa_u)\)。

用 ST 表 \(\mathcal O(1)\) 找 \(\operatorname{LCA}\)，点分树树高为 \(\log n\)，计算 \(F\) 值 \(\mathcal O(\log n)\)，加上 \(20\) 的常数，所以单次询问复杂度 \(\mathcal O(20\cdot \log^2 n)\)。

修改就正常的在点分树上修改。

code

P3920 [WC2014]紫荆花之恋

题目

树上有点权 \(r_i\) 和边权 \(c_i\)，每次往一棵树里加一个叶子，每次操作之后查询满足 \(dis(i,j)\le r_i+r_j\) 的 \((i,j)\) 点对数量。

\(n\le 10^5\)，\(r_i\le 2\times 10^9\)，\(c_i\le 10^4\)。强制在线。

由于点权数据范围限制，点分树上每个点信息只能用平衡树维护（我选择替罪羊树）。

设某个子树的根为 \(x\)，很显然的得到 \(dis(x,j)-r_j\le r_i-dis(x,i)\)，每个点就可以用两棵平衡树维护了。

发现加叶子非常难做，普通的点分树结构都是不变的，如果直接加入点分树会导致不平衡。

这时候类似替罪羊树的思想，把不平衡的子树拍扁重建。

具体的，插入叶子后，往上跳父亲，找到深度最小的点 \(x\) 满足：\(x\) 最大的儿子的 \(size\) \(\ge\) \(x\) 的 \(size\) \(\times\) \(\alpha\)。把这 \(x\) 子树的点全部拿出来重构点分树。

细节很多：

\(\alpha=0.8\) 才能在 UOJ 卡过（Luogu 评测机好快啊）；
重构点分树时要把原来每个点的平衡树删掉；
平衡树的总空间大概是 \(\mathcal O(n\log n)\) 级别的，并且要写垃圾回收；
注意不要让 \(0\) 和 \(1\) 连边；~~只有我才会犯这种错。~~
为了维护点分树上父子关系，每个点会开一个 vector 来存儿子，但是重构时一定记得修改（重构的子树的根）。

其实写的不是太丑的话，不需要特意卡常。

具体看代码。

code