点分治

树的重心(质心):最大子树最小;到所有点距离最小;

性质:

  1. 把两棵树通过一条边相连,新的树的重心在原来两棵树重心的连线上。
  2. 一棵树添加或者删除一个节点,树的重心最多只移动一条边的位置。
  3. 一棵树最多有两个重心,且相邻。
  4. 每棵子树的大小不超过 $\frac{n}{2}$

点分治

每次做子树间的信息,然后递归去做子树内的信息。

为了防止树的退化,可以在每次递归的时候找子树重心,这样保证递归层数不超过$\log n$

一般是统计路径数,需要维护所有点到根的一个信息,然后对每个子树去计算在其它子树中的贡献。还有根的贡献可能需要单独算。

动态点分治

把重心相互连接起来,构成点分树。

首先要明确原树和点分树之间的区别:点分树中的每个结点都是原树中某个子树的重心。

用点分树的结点去保存信息,这样在修改的时候只要向上跳$\log $次即可。

最后还是要明确:点分治(重心分治)的目的就是通过改变树型,使得只要$\log$次即可从根跳到叶子。并没有什么太多的技巧。


树上权值和小于等于k的路径数 poj1741

树上权值和为k的倍数的路径数 bzoj2152

树上权值和为素数的路径数 PRIMEDST

树上游戏

动态点分治:

捉迷藏

幻想乡战略游戏

模板

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
const int maxn = 1e5 + 5;
int rt, ans, treesz;
bool vis[maxn];
vector<pii> G[maxn];
int heavySonSz[maxn], sz[maxn];
vector<int> nodes;

// 找重心
// rt = 0, heavySonSz[rt] = INF, treeSz = n;
void getRoot(int u, int fa) {
sz[u] = 1, heavySonSz[u] = 0;
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i].first;
if (vis[v] || v == fa) continue;
getRoot(v, u);
sz[u] += sz[v];
heavySonSz[u] = max(heavySonSz[u], sz[v]);
}
heavySonSz[u] = max(heavySonSz[u], treesz - sz[u]);
if (heavySonSz[u] < heavySonSz[rt]) rt = u;
}

void dfsSub(int u, int fa, int val) {
// 对子树中每个点的操作
nodes.push_back(u);
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i].first;
int w = G[u][i].second;
if (vis[v] || v == fa) continue;
dfsSub(v, u, val + w);
}
}

int cal(int u, int val) {
// 遍历子树得到想要的信息
nodes.clear();
dfsSub(u, 0, val);
int ret = 0;
// 计算贡献
for (int i = 0; i < nodes.size(); i++) {

}
return ret;
}

void dfs(int u) {
vis[u] = 1;
ans += cal(u, 0);
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i].first;
if (vis[v]) continue;
ans -= cal(v, G[u][i].second); // 减去两端点在同一子树中的贡献
treesz = sz[v], rt = 0, getRoot(v, u);
dfs(rt);
}
}