点分治

 2021.02.01 19:11  2023.09.01 18:14  ACM  点分治  树 󰈭 3252字

洛谷 P3806

从一道经典的点分治问题入门

给出n个节点的树，树上的边有边权，进行m次查询，每次查询一个值k，询问是否存在一条两点间的路径使得路径上权值和为k

$n <=10^4,m<=10^2,k<=10^7, w_i<=10^4$

因为该题有多组查询，可以考虑一次点分后同时对m次查询进行处理，也可以考虑每次查询都进行一次点分。时间复杂度同为$O(nmlogn)$，但是后者因为会进行若干次点分，所以常数更大。

此外，为了能够$O(nlogn)$地进行统计，需要开设桶来加速统计结果。如果没有采用桶，而使用二分序列等方法，那么会多上一个log，应该是无法通过3806这题的，但是对于一些查询的k更大的题目，二分仍然有可取之处。故这里也贴上一份不能AC3806但是可能仍有用武之处的$O(nmlog^2n)$的代码（能顺利AC所有非TLE的点，但是正确性仍需更强的检验，使用时应更加谨慎）

$O(nmlog^2n)$代码不开桶

 1const int maxn = 1e4 + 10;
 2int n, m, k;
 3struct star{int to, next, w;};
 4int head[maxn], top = 0;
 5star edge[maxn << 1];
 6void add(int u, int v, int w){
 7    edge[top].to = v;
 8    edge[top].next = head[u];
 9    edge[top].w = w;
10    head[u] = top++;
11}
12
13//调用getroot前应该初始化S！！！
14int root = 0, S;
15int vis[maxn], sze[maxn], mx[maxn];;
16void getroot(int u, int par){
17    sze[u] = 1; mx[u] = 0;
18    for(int i = haed[u]; ~i; i = edge[i].next){
19        int to = edge[i].to; if(vis[to] || to == par) continue;
20        getroot(to, u);
21        sze[u] += sze[to];
22        mx[u] = max(mx[u], sze[to]);
23    }
24    mx[u] = max(mx[u], S - sze[u]);
25    if(mx[u] < mx[root]) root = u;
26}
27
28vector<ll> dis;
29void dfs(int u, int par, ll d){
30    for(int i = head[u]; ~i; i = edge[i].next){
31        int to = edge[i].to; if(vis[to] || to == par) continue;
32        dis.push_back({d + edge[i].w});
33        dfs(to, u, d + edge[i].w);
34    }
35}
36
37int getcnt(ll x){
38    return (int)(upper_bound(dis.begin(), dis.end(), x) - lower_bound(dis.begin(), dis.end(), x));
39}
40
41//获取经过u的答案，路径长度有基础偏移值d
42ll fun(int u, int d){
43    ll ans = 0;
44    dis.clear(); dis.push_back(d); dfs(u, 0, d);
45    sort(dis.begin(), dis.end());
46    //两条长度相同的路径和k
47    if(k % 2 == 0){
48        ll temp = getcnt(k / 2);
49        ans += temp * (temp - 1) / 2;
50     }
51    //两条长度不同的路径和为k
52    for(int i = 0; i < (int)dis.size(); i++){
53        if(dis[i] + dis[i] >= k) break;
54        ans += getcnt(k - dis[i]);
55    }
56    return ans;
57}
58
59//u是重心，考察以经过u的路径长度
60ll sove(int u){
61    //封锁u节点，分治地寻找子树.
62    vis[u] = 1; ll ans = fun(u, 0);
63    for(int i = head[u]; ~i; i = edge[i].next){
64        int to = edge[i].to; if(vis[to]) continue;
65        ans -= fun(to, edge[i].w);
66
67        S = sze[to]; root = 0;
68        getroot(to, u);
69        ans += sove(root);
70
71    }
72    return ans;
73}
74
75int main(){
76//    Fastin;
77    clr(head, -1);
78
79    int n, m; scanf("%d %d", &n, &m);
80    for(int i = 0; i < n - 1; i++){
81        int u, v, w; scanf("%d %d %d", &u, &v, &w);
82        add(u, v, w); add(v, u, w);
83    }
84    
85    mx[0] = n; root = 0;
86    while(m--){
87        scanf("%d", &k);
88        S = n; clr(vis, 0);
89        getroot(1, 0);
90        ll ans = sove(root);
91        puts(ans? "AYE": "NAY");
92    }
93    return 0;
94}

$O(nmlogn)$ 进行m次点分治开桶常数较大

 1const int maxn = 1e4 + 10;
 2int n, m, k;
 3struct star{int to, next, w;};
 4int head[maxn], top = 0;
 5star edge[maxn << 1];
 6void add(int u, int v, int w){
 7    edge[top].to = v;
 8    edge[top].next = head[u];
 9    edge[top].w = w;
10    head[u] = top++;
11}
12
13//调用getroot前应该初始化S！！！
14int root = 0, S;
15int vis[maxn], sze[maxn], mx[maxn];;
16void getroot(int u, int par){
17    sze[u] = 1; mx[u] = 0;
18    for(int i = haed[u]; ~i; i = edge[i].next){
19        int to = edge[i].to; if(vis[to] || to == par) continue;
20        getroot(to, u);
21        sze[u] += sze[to];
22        mx[u] = max(mx[u], sze[to]);
23    }
24    mx[u] = max(mx[u], S - sze[u]);
25    if(mx[u] < mx[root]) root = u;
26}
27
28vector<int> dis;
29void dfs(int u, int par, int d){
30    if(d > k) return ;
31    for(int i = head[u]; ~i; i = edge[i].next){
32        int to = edge[i].to; if(vis[to] || to == par) continue;
33        dis.push_back(d + edge[i].w);
34        dfs(to, u, d + edge[i].w);
35    }
36}
37
38//根据题目的数据范围进行修改！
39int tong[10000010];
40//获取经过u的答案，路径长度有基础偏移值d
41ll fun(int u, int d){
42    ll ans = 0;
43    dis.clear(); dis.push_back(d); dfs(u, 0, d);
44    for(int i = 0; i < (int)dis.size(); i++) if(dis[i] <= k) tong[dis[i]]++;
45    for(int i = 0; i < (int)dis.size(); i++){
46        if(dis[i] + dis[i] < k) ans += tong[k - dis[i]];
47        if(dis[i] + dis[i] == k) ans += tong[dis[i]] - 1;
48    }
49    for(int i = 0; i < (int)dis.size(); i++) if(dis[i] <= k) tong[dis[i]]--;
50    return ans;
51}
52
53//u是重心，考察以经过u的路径长度
54ll sove(int u){
55    //封锁u节点，分治地寻找子树.
56    vis[u] = 1; ll ans = fun(u, 0);
57    for(int i = head[u]; ~i; i = edge[i].next){
58        int to = edge[i].to; if(vis[to]) continue;
59        ans -= fun(to, edge[i].w);
60
61        S = sze[to]; root = 0;
62        getroot(to, u);
63        ans += sove(root);
64
65    }
66    return ans;
67}
68
69int main(){
70//    Fastin;
71    clr(head, -1);
72
73    int n, m; scanf("%d %d", &n, &m);
74    for(int i = 0; i < n - 1; i++){
75        int u, v, w; scanf("%d %d %d", &u, &v, &w);
76        add(u, v, w); add(v, u, w);
77    }
78    
79    mx[0] = n; root = 0;
80    while(m--){
81        scanf("%d", &k);
82        S = n; clr(vis, 0);
83        getroot(1, 0);
84        ll ans = sove(root);
85        puts(ans? "AYE": "NAY");
86    }
87    return 0;
88}

$O(nmlogn)$ 一次点分治同时处理m次询问开桶常数较小 (AC)

 1const int maxn = 1e4 + 10;
 2int n, m;
 3struct star{int to, next, w;};
 4int head[maxn], top = 0;
 5star edge[maxn << 1];
 6void add(int u, int v, int w){
 7    edge[top].to = v;
 8    edge[top].next = head[u];
 9    edge[top].w = w;
10    head[u] = top++;
11}
12
13//调用getroot前应该初始化S！！！
14int root = 0, S;
15int vis[maxn], sze[maxn], mx[maxn];;
16void getroot(int u, int par){
17    sze[u] = 1; mx[u] = 0;
18    for(int i = haed[u]; ~i; i = edge[i].next){
19        int to = edge[i].to; if(vis[to] || to == par) continue;
20        getroot(to, u);
21        sze[u] += sze[to];
22        mx[u] = max(mx[u], sze[to]);
23    }
24    mx[u] = max(mx[u], S - sze[u]);
25    if(mx[u] < mx[root]) root = u;
26}
27
28vector<int> dis;
29void dfs(int u, int par, int d){
30    if(d > 10000000) return ;
31    for(int i = head[u]; ~i; i = edge[i].next){
32        int to = edge[i].to; if(vis[to] || to == par) continue;
33        dis.push_back(d + edge[i].w);
34        dfs(to, u, d + edge[i].w);
35    }
36}
37
38int tong[10000010];
39int k[maxn], ans[maxn];
40//获取经过u的答案，路径长度有基础偏移值d
41void fun(int u, int d, int x){
42    dis.clear(); dis.push_back(d); dfs(u, 0, d);
43    for(int i = 0; i < (int)dis.size(); i++) if(dis[i] <= 10000000) tong[dis[i]]++;
44
45    for(int i = 0; i < (int)dis.size(); i++){
46        for(int j = 0; j < m; j++){
47            if(dis[i] + dis[i] < k[j]) ans[j] += (tong[k[j] - dis[i]]) * x;
48            if(dis[i] + dis[i] == k[j]) ans[j] += (tong[dis[i]] - 1) * x;
49        }
50    }
51    for(int i = 0; i < (int)dis.size(); i++) if(dis[i] <= 10000000) tong[dis[i]]--;
52}
53
54//u是重心，考察以经过u的路径长度
55void sove(int u){
56    //封锁u节点，分治地寻找子树.
57    vis[u] = 1; fun(u, 0, 1);
58    for(int i = head[u]; ~i; i = edge[i].next){
59        int to = edge[i].to; if(vis[to]) continue;
60        fun(to, edge[i].w, -1);
61
62        S = sze[to]; root = 0;
63        getroot(to, u);
64        sove(root);
65    }
66}
67
68int main(){
69//    Fastin;
70    clr(head, -1);
71
72    scanf("%d %d", &n, &m);
73    for(int i = 0; i < n - 1; i++){
74        int u, v, w; scanf("%d %d %d", &u, &v, &w);
75        add(u, v, w); add(v, u, w);
76    }
77    
78    for(int i = 0; i < m; i++) scanf("%d", k + i);
79
80    mx[0] = n; root = 0;
81    S = n; clr(vis, 0);
82    getroot(1, 0);
83    sove(root);
84    for(int i = 0; i < m; i++) puts(ans[i]? "AYE": "NAY");
85    return 0;
86}

本地测试洛谷提供的最大的数据跑了1s，而之前的m次点分治跑了3s；而在oj上则从371ms加速到48ms

~~还说不卡常！还说不卡常！~~

VK Cup 2012 Round 1 D

查询树上经过边数恰为k的两点路径数量，$<u, v>$与$<v, u>$计数时视为同一对点。

稍微改一下洛谷的板子即可。注意桶的范围，点数maxn

 1const int maxn = 5e4 + 10;
 2int n, k;
 3struct star{int to, next;};
 4int head[maxn], top = 0;
 5star edge[maxn << 1];
 6void add(int u, int v){
 7    edge[top].to = v;
 8    edge[top].next = head[u];
 9    head[u] = top++;
10}
11
12//调用getroot前应该初始化S！！！
13int root = 0, S;
14int vis[maxn], sze[maxn], mx[maxn];;
15void getroot(int u, int par){
16    sze[u] = 1; mx[u] = 0;
17    for(int i = haed[u]; ~i; i = edge[i].next){
18        int to = edge[i].to; if(vis[to] || to == par) continue;
19        getroot(to, u);
20        sze[u] += sze[to];
21        mx[u] = max(mx[u], sze[to]);
22    }
23    mx[u] = max(mx[u], S - sze[u]);
24    if(mx[u] < mx[root]) root = u;
25}
26
27vector<int> dis;
28void dfs(int u, int par, int d){
29    if(d > k) return ;
30    for(int i = head[u]; ~i; i = edge[i].next){
31        int to = edge[i].to; if(vis[to] || to == par) continue;
32        dis.push_back(d + 1);
33        dfs(to, u, d + 1);
34    }
35}
36
37//根据题目的数据范围进行修改！
38int tong[50010];
39//获取经过u的答案，路径长度有基础偏移值d
40ll fun(int u, int d){
41    ll ans = 0;
42    dis.clear(); dis.push_back(d); dfs(u, 0, d);
43    for(int i = 0; i < (int)dis.size(); i++) if(dis[i] <= k) tong[dis[i]]++;
44    for(int i = 0; i < (int)dis.size(); i++){
45        if(dis[i] + dis[i] < k) ans += tong[k - dis[i]];
46    }
47    if(k % 2 == 0 && tong[k / 2]) ans += tong[k / 2] * 1ll * (tong[k / 2] - 1) / 2;
48    for(int i = 0; i < (int)dis.size(); i++) if(dis[i] <= k) tong[dis[i]]--;
49    return ans;
50}
51
52//u是重心，考察以经过u的路径长度
53ll sove(int u){
54    //封锁u节点，分治地寻找子树.
55    vis[u] = 1; ll ans = fun(u, 0);
56    for(int i = head[u]; ~i; i = edge[i].next){
57        int to = edge[i].to; if(vis[to]) continue;
58        ans -= fun(to, 1);
59
60        S = sze[to]; root = 0;
61        getroot(to, u);
62        ans += sove(root);
63
64    }
65    return ans;
66}
67
68int main(){
69//    Fastin;
70    clr(head, -1);
71
72    scanf("%d %d", &n, &k);
73    for(int i = 0; i < n - 1; i++){
74        int u, v; scanf("%d %d", &u, &v);
75        add(u, v); add(v, u);
76    }
77    
78    mx[0] = n; root = 0;
79    S = n; clr(vis, 0);
80    getroot(1, 0);
81    ll ans = sove(root);
82    printf("%lld\n", ans);
83    return 0;
84}

P2634

查询路径长度为三的倍数的数量

 1const int maxn = 2e4 + 10;
 2int n;
 3struct star{int to, next, w;};
 4int head[maxn], top = 0;
 5star edge[maxn << 1];
 6void add(int u, int v, itn w){
 7    edge[top].to = v;
 8    edge[top].next = head[u];
 9    edge[top].w = w;
10    head[u] = top++;
11}
12
13//调用getroot前应该初始化S！！！
14int root = 0, S;
15int vis[maxn], sze[maxn], mx[maxn];;
16void getroot(int u, int par){
17    sze[u] = 1; mx[u] = 0;
18    for(int i = haed[u]; ~i; i = edge[i].next){
19        int to = edge[i].to; if(vis[to] || to == par) continue;
20        getroot(to, u);
21        sze[u] += sze[to];
22        mx[u] = max(mx[u], sze[to]);
23    }
24    mx[u] = max(mx[u], S - sze[u]);
25    if(mx[u] < mx[root]) root = u;
26}
27
28//根据需要的是边数还是边权修改1/edge[i].w
29vector<int> dis;
30void dfs(int u, int par, int d){
31    for(int i = head[u]; ~i; i = edge[i].next){
32        int to = edge[i].to; if(vis[to] || to == par) continue;
33        dis.push_back(d + edge[i].w);
34        dfs(to, u, d + edge[i].w);
35    }
36}
37
38//根据题目的数据范围进行修改！
39int tong[3];
40//获取经过u的答案，路径长度有基础偏移值d
41ll fun(int u, int d){
42    ll ans = 0;
43    dis.clear(); dis.push_back(d); dfs(u, 0, d);
44    for(int i = 0; i < (int)dis.size(); i++) tong[dis[i] % 3]++;
45    
46    ans += tong[0] * 1ll * tong[0] + tong[1] * tong[2] * 2;
47    
48    clr(tong, 0);
49    return ans;
50}
51
52//u是重心，考察以经过u的路径长度
53ll sove(int u){
54    //封锁u节点，分治地寻找子树.
55    vis[u] = 1; ll ans = fun(u, 0);
56    for(int i = head[u]; ~i; i = edge[i].next){
57        int to = edge[i].to; if(vis[to]) continue;
58        ans -= fun(to, edge[i].w % 3);
59
60        S = sze[to]; root = 0;
61        getroot(to, u);
62        ans += sove(root);
63    }
64    return ans;
65}
66
67int main(){
68//    Fastin;
69    clr(head, -1);
70
71    scanf("%d", &n);
72    for(int i = 0; i < n - 1; i++){
73        int u, v, w; scanf("%d %d %d", &u, &v, &w);
74        add(u, v, w); add(v, u, w);
75    }
76    
77    mx[0] = n; root = 0;
78    S = n; clr(vis, 0);
79    getroot(1, 0);
80    ll ans = sove(root);
81    ll d = gcd(ans, n * 1ll * n);
82    printf("%lld/%lld\n", ans / d, n * 1ll * n / d);
83    return 0;
84}

Conclusion

当处理一些与子树有关的问题时，可以采用点分治，比较典型的问题就是对树上满足特定限制的路径的计数。

在点分治时，每次通过选取子树的重心将当前子树进行划分，从而可以在子树之间进行复杂度较为优秀的一系列操作。

小问题

1if(sze[to] < sze[u]) S = sze[to];
2else S = sze[to] - sze[u];

在更新子树大小的时候按道理应该这样才对？？

为何洛谷上千篇一律的是直接S=sze[to]？莫非对总的时间复杂度没有过多的影响？

修改这一处后再次提交仍是TLE的TLE、AC的AC…非常的神秘

点分治