跳转至

点分治 & 点分树

点分治

点分治是解决多次询问树上点对问题最优解问题的。

首先我们直接看到这道例题：

例题

给定一棵有 \(n\) 个点的树，询问树上距离为 \(k\) 的点对是否存在。

··· （此处省略如何由暴力想到正解）

然后有一个 "神犇" 不知为什么联想到了 "分治"。

首先我们选一个点 \(x\) ，我们发现去掉这一个点之后会变成多个联通块。

然后对于任意一种可能的解 \((u,v)\) 有：

  • 两个点在同一个连通块中
  • 在不同连通块中，然后路径会经过 \(x\) 。

对于 "情况1" 我们可以递归处理，但是对于 \(x\) ，我们发现实际上就是在多个子树之中处理。

这个时候就好处理多了，我们只需要处理出当前 \(root\) 到每一个子树的距离，然后对于每一种距离打上标记，然后统计是否同时出现 \(x\) 和 \(k - x\) 这两种距离的点。

时间复杂度：\(\mathcal O(NM\log N)\)

完整代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <bits/stdc++.h>
using namespace std;
/*~~~~~~~~~~~~~~~~~~~~ Boundary Line ~~~~~~~~~~~~~~~~~~~~*/
const int N = 1e5+5;
int n,m;
int q[N],ans[N];
/*~~~~~~~~~~~~~~~~~~~~ Boundary Line ~~~~~~~~~~~~~~~~~~~~*/
struct edge{int y,w;};
vector<edge> v[N];
namespace TD{
    bitset<N> vis;

    int root; // 当前处理子问题的root
    int tot; // 当前处理连通块的大小
    int mx[N],siz[N];
    void Getroot(int x,int fa){
        mx[x]=0,siz[x]=1;
        for(auto to: v[x]){
            int y=to.y,w=to.w;
            if(y==fa || vis[y]) continue;
            Getroot(y,x);
            siz[x]+=siz[y];
            mx[x]=max(mx[x],siz[y]);
        }
        mx[x]=max(mx[x],tot-siz[x]);
        if(mx[x]<mx[root]) root=x;
    }

    const int V=1e8+5;
    bitset<V> had;
    int ed,clr[N];
    int top,dis[N];
    void Getdis(int x,int fa,int d){
        dis[++top]=d;
        for(auto to: v[x]){
            int y=to.y,w=to.w;
            if(y==fa || vis[y]) continue;
            Getdis(y,x,d+w);
        }
    }
    void Getans(int x){
        had[0]=1,ed=0,top=0;
        for(auto to: v[x]){
            int y=to.y,w=to.w;
            if(vis[y]) continue;
            top=0,Getdis(y,x,w);
            for(int i=1;i<=top;i++)
                for(int j=1;j<=m;j++)
                    if(q[j]>=dis[i]) ans[j]|=had[q[j]-dis[i]];
            for(int i=1;i<=top;i++)
                had[dis[i]]=1,clr[++ed]=dis[i];
        }
        while(ed) had[clr[ed--]]=0;
    }

    void Divide(int x){
        vis[x]=1;
        Getans(x); // 更新 ans
        for(auto to: v[x]){
            int y=to.y,w=to.w;
            if(vis[y]) continue;
            tot=siz[y],root=0;
            Getroot(y,x);
            Getroot(root,0); // 更新 siz
            Divide(root);
        }
    }
}
/*~~~~~~~~~~~~~~~~~~~~ Boundary Line ~~~~~~~~~~~~~~~~~~~~*/
signed main(){
    cin>>n>>m;
    for(int i=1;i<n;i++){
        int x,y,z;cin>>x>>y>>z;
        v[x].push_back(edge{y,z});
        v[y].push_back(edge{x,z});
    }
    for(int i=1;i<=m;i++) cin>>q[i];

    TD::mx[TD::root = 0]=1e9;
    TD::tot=n;
    TD::Getroot(1,0);
    TD::Getroot(TD::root,0);
    TD::Divide(TD::root);

    for(int i=1;i<=m;i++) 
        cout<<(ans[i]?"AYE":"NAY")<<'\n';

    return 0;
}

点分树

首先我们直接看到这道例题：

例题

在一片土地上有 \(n\) 个城市，通过 \(n-1\) 条无向边互相连接，形成一棵树的结构，相邻两个城市的距离为 \(1\)，其中第 \(i\) 个城市的价值为 \(value_i\)。

不幸的是，这片土地常常发生地震，并且随着时代的发展，城市的价值也往往会发生变动。

接下来你需要在线处理 \(m\) 次操作：

0 x k 表示发生了一次地震，震中城市为 \(x\)，影响范围为 \(k\)，所有与 \(x\) 距离不超过 \(k\) 的城市都将受到影响，该次地震造成的经济损失为所有受影响城市的价值和。

1 x y 表示第 \(x\) 个城市的价值变成了 \(y\) 。

为了体现程序的在线性，操作中的 \(x\)、\(y\)、\(k\) 都需要异或你程序上一次的输出来解密，如果之前没有输出，则默认上一次的输出为 \(0\) 。

之所以不能直接使用点分治是因为强制在线。

··· （此处省略如何由暴力想到正解）

然后什么是 "点分树" ？ 由于每一次我们选择一个重心之后就会把他们分成多个联通快。

我们连接大的重心和新的小重心：

点分树示例

变成：

(感谢题解图片)

但是我们发现这颗树好像没有什么用（完全和原树不对应）。

但是得益于点分治的性质：

  • 树的深度不超过 \(\log N\) 。
  • 对于原树上的一条路径 \((x,y)\) ，其一定经过点分树上的两个点的 LCA 。

这道题，我们本质上求得是有多少个点距离 \(x\) 小于 \(k\) ，此时我们发现如果满足 \((x,y)\) 的长度小于 \(k\) ，我们完全可以去枚举这两个点在 "点分树" 上的 LCA ，则 \(y\) 就一定是在除 \(x\) 所在子树的其他子树的节点,即：

\(ans=\sum\limits_{dis(x,lca)+dis(lca,y)\leq k ~\& ~ LCA(x,y)=lca}a_y=\sum\limits_{dis(lca,y)\leq k-dis(x,lca)~ \& ~LCA(x,y)=lca}a_y\)

此时我们相当于分两部分求解:

  1. \(lca\) (我们当前枚举到的可能的 LCA) 的所有子树中在真实树上 \(dis(y,lca) \le k-dis(x,lca)\) 的节点。
  2. \(x\) 所在 \(lca\) 子树中满足 \(dis(y,lca) \le k-dis(x,lca)\) 的节点。

第一部分我们发现只和在真实树上距离某点的距离有关，所以我们只需要对于每一颗子树建立一颗线段树，然后下标表示真实深度为 \(i\) 的节点个数，查询 \([0,k-dis(x,lca)]\)

如果第二部分我们直接查询 \([0,k-dis(x,lca)-1]\) 的话，这样就错了，因为这个 \(-1\) 在真实树上可能是完全不相近的两个点，距离不是 \(1\) ，我们当然也不能直接把 \(-1\) 替换为真实子树上的距离，因为这样计算的总距离可能会算重一部分（可能下去之后有上来）。

所以我们可以在此对于每一个子树 \(x\) 记录一颗线段树，下表表示距离 \(fa_x\) 距离为 \(i\) 的节点个数。

一切迎刃而解！！！

时间复杂度： \(\mathcal O(M \log ^2 N)\)

参考代码 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
#include <bits/stdc++.h>
#define int long long
using namespace std;
/*~~~~~~~~~~~~~~~~~~~~ Boundary Line ~~~~~~~~~~~~~~~~~~~~*/
const int N=1e5+5;
int n,m;
int a[N];
int fa[N];// 新树上的fa
/*~~~~~~~~~~~~~~~~~~~~ Boundary Line ~~~~~~~~~~~~~~~~~~~~*/

int cerr_cnt=0;

namespace TD{
    vector<int> v[N];


    int tot,root; // 当前节点数 | 当前重心
    int mx[N],siz[N];
    bitset<N> vis;
    void Getroot(int x,int fa){
        mx[x]=0,siz[x]=1;
        for(auto y: v[x]){
            if(y==fa || vis[y]) continue;
            Getroot(y,x);
            siz[x]+=siz[y];
            mx[x]=max(mx[x],siz[y]);
        }
        mx[x]=max(mx[x],tot-siz[x]);
        if(mx[x]<mx[root]) root=x;
    }

    void Divide(int x){
        vis[x]=1;
        for(auto y: v[x]){
            if(vis[y]) continue;
            tot=siz[y],root=0;
            Getroot(y,0);
            Getroot(root,0);

            fa[root]=x;

            Divide(root);
        }
    }

    void build(){
        mx[0]=1e9;
        tot=n,root=0;
        Getroot(1,0);
        Getroot(root,0);
        Divide(root);
    }
}

namespace LCA{
    vector<int> v[N];

    int fa[N][20],dep[N];
    void build(int x,int f){
        fa[x][0]=f,dep[x]=dep[f]+1;
        for(int i=1;i<=19;i++)
            fa[x][i]=fa[fa[x][i-1]][i-1];
        for(auto y: v[x]){
            if(y==f) continue;
            build(y,x);
        }
    }

    int lca(int x,int y){
        if(dep[x]<dep[y]) swap(x,y);
        for(int i=19;i>=0;i--)
            if(dep[fa[x][i]]>=dep[y])
                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 query(int x,int y){
        int lc=lca(x,y);
        return dep[x]+dep[y]-2*dep[lc];
    }
}

struct TREE{
    #define lc T[p].ls
    #define rc T[p].rs

    int root[N],cnt;
    struct {int ls,rs,sum;} T[N*50];
    void change(int &p,int l,int r,int x,int y){
        if(!p) p=++cnt;
        T[p].sum+=y;
        if(l==r) return;

        int mid=l+r>>1;
        if(x<=mid) change(lc,l,mid,x,y);
        else change(rc,mid+1,r,x,y);
    }
    int query(int p,int l,int r,int x,int y){
        if(!p) return 0;
        if(x<=l && r<=y) return T[p].sum;

        int mid=l+r>>1,ans=0;
        if(x<=mid) ans+=query(lc,l,mid,x,y);
        if(y>mid) ans+=query(rc,mid+1,r,x,y);
        return ans;
    }
};
TREE T1,T2;

void update(int x,int y){ // 将 x 节点权值增加 y
    int p=x;
    while(p){
        T1.change(T1.root[p],0,N,LCA::query(p,x),y);
        T2.change(T2.root[p],0,N,LCA::query(fa[p],x),y);
        p=fa[p];
    }
}
int query(int x,int k){
    int p=x,lst=0,ans=0;
    while(p){
        ans+=T1.query(T1.root[p],0,N,0,k-LCA::query(p,x));
        if(lst) ans-=T2.query(T2.root[lst],0,N,0,k-LCA::query(p,x));
        lst=p,p=fa[p];
    }
    return ans;
}

/*~~~~~~~~~~~~~~~~~~~~ Boundary Line ~~~~~~~~~~~~~~~~~~~~*/
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];

    for(int i=1;i<n;i++){
        int x,y;cin>>x>>y;
        TD::v[x].push_back(y);
        TD::v[y].push_back(x);
        LCA::v[x].push_back(y);
        LCA::v[y].push_back(x);
    }

    TD::build();
    LCA::build(1,0);

    for(int i=1;i<=n;i++)
        update(i,a[i]);

    int last_ans=0;
    while(m --> 0){
        int op,x,y;cin>>op>>x>>y;
        x^=last_ans,y^=last_ans;

        if(op==0) cout<<(last_ans=query(x,y))<<'\n';
        else{
            update(x,y-a[x]);
            a[x]=y;
        }
    }

    return 0;
}

注意事项

  • 线段树的范围应当根据题目调整为从 \(0\) 开始
  • TD::build() 中记得先调用两次求出最开始的重心和子树大小 siz[] ，从而保证时间复杂度。