【笔记分享】点分树及其应用

· · 算法·理论

点分树

定义

点分树是也可以称为重心重构树，是基于原树重心重构。如下图。

点分树是在重心剖分过程中每一个找到的重心，将上一层剖分时的重心设为它的父亲 ，得到一颗大小不变、最多 log(n) 层的重构树。

性质

用点分树解决问题主要是利用性质二。比如要统计与 x 出发的所有点对信息 \sum\limits_{x\neq y} dis(x,y), 要找到所有的 x,y，在点分树上，向上不停跳 x 的祖先，每层祖先就是 x 到其他被该祖先分割的 y 的 lca。因为树高是 log，因此经过 log 次统计就可以算出所有 y 的贡献。《换个说法》点分树的每一层都是原树一个连通块的重心，以该点为根来收集连通块内的信息统一进行统计，当向上走时，就如上图最右边相当于离开了当前连通块到一个更大的连通块。

点分树上的容斥。利用点分树统计信息时的一般过程是从下到上逐层统计。当离开当前子树向上时，需要容斥掉当前子树对答案的重复贡献，这个过程与点分治统计答案时的容斥相似。

具体通过几道题目来理解。

例题一：P6329【模板】点分树 / 震波

题意

一颗带点权树，有两种操作：修改 x 的点权，查询与点 x 距离不超过 K 的点权值之和。

解析

如果不考虑修改，如何查询 x 出发距离不超过k的点权和？我们需要先找出所有 dis(x,y)\leq k 的 y，然后累加点权即可。具体的：还是考虑点分治处理，对于当前重心 u,先收集 u 子树每个点，每个点两个值：到 u 的 dis 和点权 w。将每个点信息用数据结构 T 存起来。 然后对于每个点 i，在 T 中查找所有 dis(u,i)\leq k-dis(u,i) 的 i，将这些 i 的点权累加即可。 在这里，数据结构可以时一般序列+排序+前缀和+二分查找即可。显然这里的统计有重复，属于同一子树内的点对会重复统计，因此我们在 u 统计后，进入 u 的儿子 v 时减去重复统计的部分（容斥）。

再考虑修改。为了支持修改，我们将上面的数据结构换为线段树或者树状数组（支持单点修改、前缀和查询）。 首先，我们只考虑某一重心 u 的子树，假设我们已经提前收集好了 u 子树每个点的 dis 和 w，并以 dis(u,i) 为下标，对应的 w_i 为值建立了一颗线段树 T1。在当前子树要查询一个点 x 出发不超过k的点权和，只需要在 T1 中 [1,k-dis(u,x)] 范围求和即可。 其次，容斥如何处理呢？与前面一致，我们以 dis(fa[u],i) 为下标，对应的 w_i 为值建立了一颗线段树 T2,其中 fa[u] 是 u 的上一层重心。 同样 在T2 上查询 [1,k-dis(u,x)] 范围的和减去即可。

接下来就是修改。还是考虑在当前子树 u 中，某个点 x 的点权 w_x+v 。我们只需要在 T1 中修改 dis(u,x) 位置 +v ,在 T2 中修改 dis(fa[u],x) 位置的点权为 w_x。

为了保证一致性与复杂度，我们按原树的重心重构得到点分树，在点分树上的每个点建立两颗线段树 T1,T2 ，分别维护子树内的点对信息。

点分树的构建

按上面的分析，我们在修改点 x 时，需要逐层向上修改每一层的重心上的线段树。因此构建点分树只需要记住每个重心的上层重心即可。具体如下：

void divcent(int u){
    vis[u]=1;
    for(int v:g[u]){
        if(vis[v])continue;
        sum = siz[v];msiz[rt=0]=n;
        getrt(v , u); //查找子树重心
        f[rt]=u;    //记录每层重心的父节点
        divcent(rt);
    }
}

计算树上的两点距离

可以在原树上预处理LCA，然后 dis(x,y)=dep[x]+dep[y]-2\cdot dep[lca(x,y)]。

修改点权

修改点权时，只需要在原树上修改点 x 的点权为 w_x+v，然后在点分树的每一层的线段树中修改 dis(u,x) 位置的点权为 w_x，在 T2 中修改 dis(fa[u],x) 位置的点权为 w_x+v。

void update(int x,int v){
    int now = x;
    while(now){
        t1.update(t1.rt[now] , 1 , n, getdis(x,now)+1 , v);//t1上加权重
        if(f[now])t2.update(t2.rt[now],1,n,getdis(x, f[now])+1 , v);
        now=f[now];
    }
}

查询 x 的答案

查询 x 的答案时，只需要在 T1 中查询 [1,k-dis(u,x)] 范围的和，在 T2 中查询 [1,k-dis(fa[u],x)] 范围的和，然后容斥即可。

int query(int x,int k){
    int now=x, ret=0;
    while(now){         
        if(getdis(x,now) <= k)//T1查询
            ret+= t1.ask(t1.rt[now], 1,n, 1 , k-getdis(x,now)+1);
        if(f[now] && getdis(x,f[now]) <= k)//T2容斥
            ret-= t2.ask(t2.rt[now],1,n,1,k-getdis(x,f[now])+1);        
        now=f[now];
    }
    return ret;
}

总结算法

:::success[完整代码参考]

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+100;
const int M=5e6+100;
struct seg{
    int rt[N];
    int tot,lc[M],rc[M],s[M];
    void pushup(int p){s[p]=s[lc[p]] + s[rc[p]]; }
    void update(int& p,int l,int r,int k,int v){
        if(!p)p=++tot;
        if(l==r){s[p]+=v;return;}
        int mid=(l+r)>>1;
        if(k<=mid)update(lc[p],l,mid,k,v);
        else update(rc[p],mid+1,r,k,v);
        pushup(p);
    }
    int ask(int p,int l,int r,int ql,int qr){
        if(!p)return 0;
        if(ql<=l && r<=qr)return s[p];
        int mid=(l+r)>>1;
        int ret=0;
        if(ql<=mid)ret+=ask(lc[p],l,mid,ql,qr);
        if(mid<qr)ret+=ask(rc[p],mid+1,r,ql,qr);
        return ret;
    }
}t1,t2;
int n,m,rt,sum,val[N],msiz[N],siz[N],vis[N];
int dis[N],fa[N][20];
int f[N];//重构树父亲表示法
vector<int>g[N];
void dfs(int x,int ff){
    fa[x][0]=ff;
    for(int j=1;(1<<j)<=dis[x];j++)
        fa[x][j]=fa[fa[x][j-1]][j-1];
    for(auto v:g[x]){
        if(v==ff)continue;
        dis[v]=dis[x]+1;
        dfs(v,x);       
    }
}
int lca(int x,int y){
    if(dis[x]<dis[y])swap(x,y);
    int k=dis[x]-dis[y];
    for(int i=0;(1<<i)<=k;i++) 
        if(k&(1<<i))x=fa[x][i];
    if(x==y)return x;
    for(int i=19;i>=0;i--){
        if(fa[x][i]!=fa[y][i])
            x=fa[x][i],y=fa[y][i];
    }
    return fa[x][0];
}
int getdis(int x,int y){return dis[x]+dis[y]-2*dis[lca(x,y)];}

void getrt(int u,int ff){//cerr<<u<<endl;
    siz[u]=1;msiz[u]=0;
    for(int v:g[u]){
        if(v==ff || vis[v]) continue;
        getrt(v,u);
        msiz[u]=max(msiz[u],siz[v]);
        siz[u]+=siz[v];
    }
    msiz[u]=max(msiz[u],sum-siz[u]);
    if(msiz[u] < msiz[rt]) rt=u;
}   
void divcent(int u){
    vis[u]=1;
    for(int v:g[u]){
        if(vis[v])continue;
        sum = siz[v];msiz[rt=0]=n;
        getrt(v , u); 
        f[rt]=u;
        divcent(rt);
    }
}
void update(int x,int v){
    int now = x;
    while(now){
        t1.update(t1.rt[now] , 1 , n, getdis(x,now)+1 , v);//t1上加权重
        if(f[now])t2.update(t2.rt[now],1,n,getdis(x, f[now])+1 , v);
        now=f[now];
    }
}
int ask(int x,int k){
    int now=x, ret=0;
    while(now){         
        if(getdis(x,now) <= k)
            ret+= t1.ask(t1.rt[now], 1,n, 1 , k-getdis(x,now)+1);
        if(f[now] && getdis(x,f[now]) <= k)
            ret-= t2.ask(t2.rt[now],1,n,1,k-getdis(x,f[now])+1);        
        now=f[now];
    }
    return ret;
}
int main(){
    //freopen("1.txt","r",stdin);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>val[i];
    for(int i=1;i<n;i++){
        int u,v;cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1,0);//getlca   
    msiz[rt=0]=sum=n;
    getrt(1,0);      
    divcent(rt);//点分树

    for(int i=1;i<=n;i++)update(i,val[i]);
    int lastans=0;
    for(int i=1;i<=m;i++){
        int op,x,y;
        cin>>op>>x>>y;
        x^=lastans;y^=lastans; 
        if(op==1){
           update(x,y-val[x]);
           val[x]=y;
        }else{
            lastans=ask(x,y);
            cout<<lastans<<"\n";
        }
    }
    return 0;
}

:::

小结：第一题我们学习了点分树解决问题的一般过程，了解了点分树的来源，下面我们就用点分树思想与性质来解决下面的题目。

P10603 BZOJ4372 烁烁的游戏

题意

给一棵 n 个结点的树，边权均为 1，初始点权均为 0。进行 m 次操作：

Q x：询问结点 x 的点权。 M x d w：将树上与结点 x 距离不超过 d 的节点的点权均加上 w。

解析

本题与上一题不同的地方在于区间修改，单点查询。

点分树是解决 树上连通块信息问题 的利器。与前面的套路相同，我们在点分树上每个点 建立数据结构维护信息。在 修改/查询时 从下到上 遍历点分树上的祖先并 修改/查询 这些点上的数据结构信息。通常每个点需要建立多个数据结构，用容斥原理来防止部分答案被重复计算。

本题，我们在点分树上每个点同样建立两颗线段树 T1,T2。同样的 T1 维护当前重心下 每个距离值的点权，T2 维护点分树上每个点到当前点的父亲的距离的点权。

查询时，从 x 开始，查询每层祖先上面的线段树对 x 的贡献，通过容斥计算求和。

修改时，从 x 开始，修改稿每层祖先的线段树 x 对他们的贡献。具体的，设当前重心为 u, x对 u.T1 的 d-dis(x,u) 位置贡献了 w，则 u.T2 上 d-dis(x,f(u))+1 位置也贡献了 w。（区间修改）

查询时，从 x 开始，查询每层祖先上面的线段树对 x 的贡献，通过容斥计算求和。（单点查询）
修改与查询参考：

int ask(int x,int k){
    int ret = t1.ask(t1.rt[x],0,n, 0);//自己的贡献
    for (int now=x; f[now]; now=f[now]){  
        int dist = getdis(x,f[now]);
        ret += t1.ask(t1.rt[f[now]], 0,n,  dist );//加上父亲节点的T1 贡献
        ret -= t2.ask(t2.rt[now], 0,n,  dist); //容斥掉当前树的T2  贡献     
    }
    return ret;
}
void update(int x,int k ,int v){
    t1.update(t1.rt[now] , 0 , n, 0,k , v);//对自己子树的贡献范围[0,k]
    for(int now=x; f[now]; now=f[now]){
        int dist = getdis(x,f[now]);
        if(dist > k)continue;
        t1.update(t1.rt[f[now]] , 0 , n, 0,k-dist , v);//对父亲T1的贡献范围[0,k-dist]
        t2.update(t2.rt[now] , 0 , n, 0,k-dist , v);//对当前树T2贡献范围[0,k-dist]
    }
}

因为数据结构只需要支持区间修改单点查询，也可以通过差分变为单点修改，区间查询。通过动态树状数组来实现，具体参考下面详细代码： :::success[完整代码参考]

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
typedef long long ll;
struct BIT{//支持维护[0,n]范围，内部向右偏移一位
    vector<int>c;    int siz;
    void init(int n){c.resize(n+2);siz=n+1;}
    void add(int k, int d) {  
        k++;       
        for (; k <=siz; k += (k & -k)) 
            c[k] += d;
    }
    int query(int k){
        int ret = 0;
        k++;
        for(; k>0 ; k -= (k&-k))
            ret += c[k];
        return ret;
    }
}t1[N],t2[N];
int n,m,rt,sum,val[N],msiz[N],siz[N],vis[N];
int f[N];//重构树父亲表示法
vector<int>g[N];
namespace LCA{
    int dis[N],fa[N][20];    
    void dfs(int x,int ff){
        fa[x][0]=ff;
        for(int j=1;(1<<j)<=dis[x];j++)
            fa[x][j]=fa[fa[x][j-1]][j-1];
        for(auto v:g[x]){
            if(v==ff)continue;
            dis[v]=dis[x]+1;
            dfs(v,x);       
        }
    }
    int lca(int x,int y){
        if(dis[x]<dis[y])swap(x,y);
        int k=dis[x]-dis[y];
        for(int i=0;(1<<i)<=k;i++) 
            if(k&(1<<i))x=fa[x][i];
        if(x==y)return x;
        for(int i=19;i>=0;i--){
            if(fa[x][i]!=fa[y][i])
                x=fa[x][i],y=fa[y][i];
        }
        return fa[x][0];
    }
    int getdis(int x,int y){return dis[x]+dis[y]-2*dis[lca(x,y)];}
}
void getrt(int u,int ff){
    siz[u]=1;msiz[u]=0;
    for(int v:g[u]){
        if(v==ff || vis[v]) continue;
        getrt(v,u);
        msiz[u]=max(msiz[u],siz[v]);
        siz[u]+=siz[v];
    }
    msiz[u]=max(msiz[u],sum-siz[u]);
    if(msiz[u] < msiz[rt]) rt=u;
}   
void divcent(int u){
    vis[u]=1;
    for(int v:g[u]){
        if(vis[v])continue;
        sum = siz[v];msiz[rt=0]=n;
        getrt(v , u); 
        f[rt]=u;
        t2[rt].init(siz[u]); 
        divcent(rt);
    }
    t1[u].init(siz[u]);    
}
void update(int u,int k,int v){
    t1[u].add(0,v);t1[u].add(k+1,-v);   
    for(int now=u ; f[now] ; now=f[now]){
        int d = LCA::getdis(u,f[now]);
        if(k < d)continue;
        t1[f[now]].add(0,v);t1[f[now]].add(k-d+1,-v);
        t2[now].add(0,v);t2[now].add(k-d+1 , -v);
    }
}
int query(int u){
    int ret=t1[u].query(0);
    for(int now=u ; f[now] ; now=f[now]){
        int d = LCA::getdis(u,f[now]);
        ret += t1[f[now]].query(d);
        ret -= t2[now].query(d);
    }
    return ret;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);      g[v].push_back(u);
    }
    LCA::dfs(1,0);

    msiz[rt=0]=sum=n;
    getrt(1,0);      
    divcent(rt);//点分树，并为每个点初始化2颗树状数组

    for(int i=1;i<=m;i++){
        char p;int x,k,v;
        cin>>p>>x; 
        if(p=='Q'){
            cout<<query(x)<<"\n";
        }else{
            cin>>k>>v;
            update(x,k,v);
        }
    }
    return 0;
}

:::

例题三：P3345 [ZJOI2015] 幻想乡战略游戏

题意

有一颗 n 节点带边权与点权 d_i 的无根树，选定一个点为根，树的权值为 \sum (dist(root,i)+d_i) 。点权可以修改，询问每次修改后树的权值最小。

解析

换根的思路。本题是找最佳决策点问题，一个暴力的做法，枚举每个点作为决策点，计算 \sum dist(rt,i)*d_i ，取最小值。为了需求优化，我们观察如果将决策点从 u 变化到 儿子 v 的变化。

设 Sum_v=\sum\limits_{i\in T_v} d_i 表示子树 v 内所有点到 v 的点权和。

则从 u 到 v 时，子树 v 的权值和减少 w_{<u,v>} \cdot Sum_v, 子树 v 外的点的权值和增加 w_{<u,v>} \cdot (Sum_u-Sum_v)。

总的变化为： w_{<u,v>}*(2*Sum_v-Sum_u) 。

于是我们得出一个**做法：从根节点开始，如果存在儿子节点的答案更优，则转移到儿子节点，直到无法转移为止**。 整个换根过程的复杂度与深度相关，**用点分树**可以优化到 $O(n\log n)$。 在点分树上记录 $3$ 个值： - $sum_v=\sum\limits_{i \in T_v} d_i$ 表示子树 $v$ 内所有点的点权和。 - $f_v=\sum\limits_{i \in T_v} dist(i,v)\cdot d_i$ 表示当 $v$ 为决策点时子树 $v$ 的代价。 - $g_v=\sum\limits_{i \in T_v} dist(i,fa[v])\cdot d_i$ 表示当 $fa[v]$ 为决策点时子树 $v$ 的代价。 总结算法如下： - 对原树重构一颗点分树。 - 点分树上每个点维护 $sum_v,f_v,g_v$。 - 每次修改点权时，从修改点开始，向上更新 $sum_v,f_v,g_v$。 - 每次查询时，从点分树的树根开始，计算当前点作为决策点的总代价。如果儿子节点更优，则转移到儿子节点。 :::success[核心代码参考] ```c++ void update(int u,int val){//修改 sum[u]+=val; for(int i=u;fa[i];i=fa[i]){//fa[i]是重构树上的父节点 ll d=getdis(fa[i],u); f[fa[i]] += d*val; g[i] += d*val; sum[fa[i]] += val; } } ll calc(int u){ //计算点u为决策点时的总代价，向上计算每个祖先除去当前u的子树外的其他子树代价 ll ans=f[u]; for(int i=u;fa[i];i=fa[i])//向上计算时，减去当前子树u的代价，再加上子树外的节点增加的代价 ans += f[fa[i]] - g[i] + getdis(fa[i],u)*(sum[fa[i]]-sum[i]); return ans; } ll query(int u){//查询当前子树的最优值 ll ans=calc(u); for(auto e:G[u] ){ int v = e.to; //点分树上的儿子 int son = e.son; //原树上的儿子 if(calc(son) < ans)ans=calc(v);//原树上转移到儿子更优 } return ans; } ``` ::: ## 例题四：[P2056 [ZJOI2007] 捉迷藏](https://www.luogu.com.cn/problem/P2056) ### 题意 有一颗 $n$ 节点的无根树，每个点有 `0,1` 两种状态，初始都为 `0`。每次对一个点状态取反，询问当前树上状态为 `0` 的点对最远距离。 ### 解析 对于只考虑询问可以用树形DP或点分治来完成。 先考虑不带修改的点分治做法：分治到当前节点 $u$ 时，如树形DP求直径的做法一样，在 $u$ 上维护一个最长链与次长链。考虑到当前儿子 $v$ 时用 $\max\limits_{i\in T_v}(dist(i,u))$ 更新 $u$ 最长链与次长链。 现在考虑带修改的情况。点分树上，我们就需要找到一个数据结构维护最大值，支持插入删除的数据结构——可删除堆。每个节点维护两个堆 $H1,H2$，$H1$ 维护子树 $u$ 内所有 `0` 点到 $fa[u]$ 的距离(点分树上父亲)，$H2$ 维护子树 $u$ 所有儿子的 $H1$ 的最大值。 显然，经过**当前 $u$ 的最长链为 $H2$ 的最大值与次大值的和**。 本题每次是对整棵树进行查询一个最大值，可以用一颗堆 $H$ 来维护经过每个点的最长链。 ### 算法流程 - 建立点分树，点分树上每个点维护两个带删除堆 $H1,H2$。 - 每次修改点权时，从修改点开始，向上更新 $H1,H2$，以及整颗树的 $H$。 - 每次查询时，取 $H$ 的最大值即可。 ## 例题五：[P14622 [2019 KAIST RUN Fall] Wind of Change](https://www.luogu.com.cn/problem/P14622) ### 题意 有两颗带边权的树$T1,T2$，对于每个点$i$计算$D(i)=\min_{j\not =i}(dis1(i,j)+dis2(i,j))$。 $n\le 2\times 10^5

解析

因为 dist(x,y)=dist(x,u)+dist(y,u)，则:

=min\{dist1(i,u)+dist1(r,j)+dist2(rt,i)+dist2(rt,j)\} \\ =min\{dist1(u,j)+dist2(rt,j)\}+dist1(u,i)+dist2(rt,i)

点分治擅长通过分治的方式找到 \log 个 u。

对 T1 点分治到当前根节点 u ，收集 u 子树中所有点到 u 的距离 dist1[i]，存入序列 C 中。 然后将序列中的每个点 i ， 在 T2 中的 i 的祖先链上每个点 p 上维护一个（dist1[j]+dist2(j,p)）最小值与次小值 。

如下示意图：

然后再查询序列 C 中每个点 i 的 D(i) 时，在 T2 的 i 的祖先链查询除 i 外的 \min\{dist1[j]+dist2(j,p)\}。D(i)=dist1(u,j)+dist2(rt,j)+dist1(u,i)+dist2(rt,i)。对 T2 进行重心重构可以优化跳链的过程。 如下示意图： 总结算法如下:

练习

P10604/BZOJ4317 Atm 的树

P3241 [HNOI2015] 开店