点分治 学习笔记

模板及讲解

点分治

点分治就是处理树上路径的一个树上分治算法。
其基本思路与分治类似。

模板题

Poj 1741

给出一颗无根树,求树上距离小于等于 $k$ 的点对(路径)有多少个。
$n \leq 10000$

基本思路

点分治基本步骤:
1、DFS 每一棵子树 (以重心为根保证复杂度)
2、对当前 DFS 的子树进行求值 (calc)
3、求值完删除当前重心继续往下 DFS 子树,顺便对子树进行求值后容斥

求值方法 (因题而异,用 Poj 1741 为例):
1、DFS 求出所有连通点到当前子树根的距离
2、将距离排序,用两点法等对信息进行处理

点分治核心函数是 calc

代码实现

函数

  • void dfs(int u):DFS 求解子树,根为 $u$
  • int calc(int u, int D):计算以$u$为根子树的答案,$(fa[u], u)$边权为$D$
  • void dfsD(int u, int D, int fa):计算以$u$为根子树节点到 $u$ (根)的距离数组,$D,fa$为临时局部变量
  • void getRt(int u, int fa):求解以$u$为根的子树的重心

    代码

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 10000 + 5;
const int INF = 2147483647;
struct edge {
int v, w, nxt;
}ed[MAXN * 2];
int n, k, ans, en, hd[MAXN];
int vis[MAXN], siz[MAXN], rt, wt[MAXN], Tsz; // 访问数组 (点分治中删除的点设为 1),子树大小,当前根,以 i 为重心的最大深度(用作求重心),当前树大小
int arr[MAXN], cnt; // 距离数组 arr ,在 dfsD() 和 calc() 中使用
void ins(int u, int v, int w) {ed[++en] = (edge){v, w, hd[u]}, hd[u] = en;}
void getRt(int u, int fa) { // 找 u 子树的重心
siz[u] = 1; wt[u] = 0;
for (int i = hd[u]; i > 0; i = ed[i].nxt) {
edge &e = ed[i];
if (e.v != fa && !vis[e.v]) getRt(e.v, u), siz[u] += siz[e.v], wt[u] = max(wt[u], siz[e.v]);
}
wt[u] = max(wt[u], Tsz - siz[u]);
if(wt[rt] > wt[u]) rt = u;
}
void dfsD(int u, int D, int fa) { // DFS 求子树到 u (根)的距离数组 arr
arr[++cnt] = D;
for (int i = hd[u]; i > 0; i = ed[i].nxt) {
edge &e = ed[i];
if (e.v != fa && !vis[e.v]) dfsD(e.v, D + e.w, u);
}
}
int calc(int u, int D) { // 计算 u 子树的答案,(fa[u], u) 边权为 D
cnt = 0; dfsD(u, D, 0); // 计算 子树到 u (根)的距离数组 arr
int l = 1, r = cnt, sum = 0;
sort(arr + 1, arr + cnt + 1);
for( ; ; ++l) {
while (r && arr[l] + arr[r] > k) --r;
if(r < l) break;
sum += r - l + 1;
} // 两点法求答案
return sum;
}
void dfs(int u) { // DFS 求解
ans += calc(u, 0); // 求解当前树
vis[u] = 1; // 记录当前删除标记
for (int i = hd[u]; i > 0; i = ed[i].nxt) {
edge &e = ed[i];
if (!vis[e.v]) {
ans -= calc(e.v, e.w); // 容斥,减去无用答案
rt = 0, Tsz = siz[e.v], getRt(e.v, 0); // 找子树的重心作为子树根来进行下一步求解
dfs(rt);
}
}
}
void clean() {
ans = en = 0, ms(hd, -1), ms(vis, 0), ms(wt, 0);
}
int solve() {
clean();
for (int u, v, w, i = 1; i < n; ++i) scanf("%d%d%d", &u, &v, &w), ins(u, v, w), ins(v, u, w);
wt[0] = INF, Tsz = n, getRt(1, 0); // 第一次找重心作为根
dfs(rt);
printf("%d\n", ans - n); // 减去一个点单独成路径
return 0;
}
}
int main() {
while(scanf("%d%d", &flyinthesky::n, &flyinthesky::k) == 2 && (flyinthesky::n || flyinthesky::k)) flyinthesky::solve();
return 0;
}

例题

树上距离为 $ k $ 的点对

Luogu 3806

询问树上距离为 $ k $ 的点对是否存在。

解:直接上点分治,算答案的时候用桶存答案,然后乘法原理即可。
每次询问做一次点分治或者打表。注意边权为 0 的情况

Ps:CF 161D 数据更强

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 10000 + 5;
const int INF = 2147483647;
struct edge {
int v, w, nxt;
}ed[MAXN * 2];
int n, q, k, en, hd[MAXN];
int vis[MAXN], wt[MAXN], Tsz, rt, siz[MAXN];
int cnt, arr[MAXN], tax[10000005], whw[10000005];
LL ans;
void ins(int u, int v, int w) {ed[++en] = (edge){v, w, hd[u]}, hd[u] = en;}
void getRt(int u, int fa) {
wt[u] = 0, siz[u] = 1;
for (int i = hd[u]; i > 0; i = ed[i].nxt) {
edge &e = ed[i];
if (e.v != fa && !vis[e.v]) getRt(e.v, u), siz[u] += siz[e.v], wt[u] = max(wt[u], siz[e.v]);
}
wt[u] = max(wt[u], Tsz - siz[u]);
if (wt[rt] > wt[u]) rt = u;
}
void dfsD(int u, int fa, int D) {
arr[++cnt] = D;
for (int i = hd[u]; i > 0; i = ed[i].nxt) {
edge &e = ed[i];
if (e.v != fa && !vis[e.v]) dfsD(e.v, u, D + e.w);
}
}
LL calc(int u, int D) {
cnt = 0; dfsD(u, 0, D);
LL sum = 0;
for (int i = 1; i <= cnt; ++i) ++tax[arr[i]];
for (int i = 1; i <= cnt; ++i) {
if (!whw[arr[i]] && k >= arr[i]) {
if (arr[i] == k - arr[i]) sum += tax[arr[i]] * (tax[arr[i]] - 1) / 2; // 写对两两配对不重复的公式
else sum += tax[k - arr[i]] * tax[arr[i]];
whw[arr[i]] = 1, whw[k - arr[i]] = 1;
}
}
for (int i = 1; i <= cnt; ++i) --tax[arr[i]];
for (int i = 1; i <= cnt; ++i) {
whw[arr[i]] = 0;
if (k >= arr[i]) whw[k - arr[i]] = 0;
}
return sum;
}
void dfs(int u) {
ans += calc(u, 0);
vis[u] = 1;
for (int i = hd[u]; i > 0; i = ed[i].nxt) {
edge &e = ed[i];
if (!vis[e.v]) {
ans -= calc(e.v, e.w);
rt = 0, Tsz = siz[e.v], getRt(e.v, u);
dfs(rt);
}
}
}
void clean() {
en = 0, ms(hd, -1), ms(tax, 0);
}
int solve() {
scanf("%d%d", &n, &q);
clean();
for (int u, v, w, i = 1; i < n; ++i) scanf("%d%d%d", &u, &v, &w), ins(u, v, w), ins(v, u, w);
while (q--) {
ans = 0, ms(vis, 0);
scanf("%d", &k);
rt = 0, Tsz = n, wt[0] = INF, getRt(1, 0);
dfs(1);
printf("%s\n", ans > 0 ? "AYE" : "NAY");
}
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
/*
5 50
1 2 3
1 3 1
1 4 2
3 5 1
4
2 100
1 2 0
0
*/

树上距离模 $ k $ / 是 $ k $ 的倍数的点对

Bzoj 2152

询问树上距离是 $ k $ 的倍数的点对。

解:直接上点分治,算答案的时候用桶存答案,然后乘法原理即可。
是 $ k $ 的倍数相当于模$ k $为 $ 0 $

常见题型

------ 本文结束 ------