分治是一种将大的问题拆分成更小的问题并分而治之的算法，有利于使一个大的问题迅速缩小。在线性区间上的分治一般从区间中点将区间一分为二（这个中点也叫做分治中心），这样分 \(\log n\) 次就能使区间大小缩小到 \(1\)。而在树上的分治一般以树的重心作为分治中心，这样分 \(\log n\) 次也能将范围缩小到单个节点，这就是点分治。作为一种分治算法，点分治的主要功能是使一个大的问题迅速缩小，这样就能将一些趋近于暴力的算法成功地在每个小问题上应用了。
比较简单的点分治题常关于解决树上点对问题，而更难的点分治题会涉及到各种树上问题，但这些问题大部分都和树的局部形态不相关。
例题
例题：Luogu P3806 【模板】点分治1
这就是点分治最简单的应用：树上点对问题。
首先考虑暴力的做法是 \(O(n^2\log n)\) 枚举每两个点的 LCA，然后再算距离。
还有一种做法就是以任意节点为根，建立一棵树，对于每个根节点，枚举以该节点为 LCA 的路径，即求出子节点的深度，看有没有两个加起来等于 \(k\)。这种算法的复杂度为 \(O(n^2)\)。
这种算法的本质是先求过根节点的链，再求不过根节点的链。所有不过根节点的链都只会经过其所在的唯一子树。换句话说，其实访问子树时只和子树的形态有关，与上面部分的形态无关。这样的方法其实是先求经过整棵树的答案，再求每棵子树内部的答案。这不就是分治吗？
这时我们思考这种方法的瓶颈：每一次询问子树时，我们都要从以固定根节点得出的子树的根作为分治中心，这样子节点的不均匀性可能导致分治的规模缩小地太慢。因为只和子树的形态有关，所以我们可以在子树上再重新选择一个根节点并计算，这样就可以保证规模缩小的速度了。
那究竟要选哪个点作为分治中心呢？要让规模缩小地最快，要让每次分治时分出来最大的子树尽量小，于是树的重心满足这个条件。事实上，选择树的重心作为分治中心复杂度为 \(O(n\log n)\)。
做法就出来了：每次分治时，遍历分治中心的所有子树，用一个桶存储子树内每个节点的深度，再对于每个节点通过桶查询与之深度和为 \(k\) 的点是否存在。完成后，删除当前节点，为每个子树找到分治中心，递归进行分治处理。
上代码！
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 10005, MAXM = 105, MAXK = 10000005;
struct edge {
int to, val;
};
vector<edge> to[MAXN];
bool vis[MAXN];
int n, m, k[MAXM], size[MAXN], root, rootm, tot;
void getroot(int x, int fa = 0x3f3f3f3f) {
int curm = 0;
size[x] = 1;
for (edge p: to[x]) {
if (p.to == fa || vis[p.to]) continue;
getroot(p.to, x);
size[x] += size[p.to];
curm = max(curm, size[p.to]);
}
curm = max(curm, tot - size[x] - 1);
if (curm < rootm) {
rootm = curm;
root = x;
}
}
int ans[MAXK], t[MAXK];
void dfs(int x, int fa = 0x3f3f3f3f, int pres = 0) {
// printf(" DFS %d PRES = %d\n", x, pres);
for (int i = 1;i <= m;i++){
if (pres <= k[i]) ans[i] += t[k[i] - pres];
}
for (edge p: to[x]) {
if (p.to == fa || vis[p.to]) continue;
dfs(p.to, x, pres + p.val);
}
}
void calc(int x, int fa = 0x3f3f3f3f, int pres = 0) {
// printf(" CALC %d PRES = %d\n", x, pres);
if (pres <= MAXK) t[pres] += 1;
for (edge p: to[x]) {
if (p.to == fa || vis[p.to]) continue;
calc(p.to, x, pres + p.val);
}
}
void clear(int x, int fa = 0x3f3f3f3f, int pres = 0) {
if (pres <= MAXK) t[pres] = 0;
for (edge p: to[x]) {
if (p.to == fa || vis[p.to]) continue;
clear(p.to, x, pres + p.val);
}
}
void solve(int x) {
t[0] = 1;
vis[x] = true;
for (edge p: to[x]){
if (vis[p.to]) continue;
dfs(p.to, 0x3f3f3f3f, p.val);
calc(p.to, 0x3f3f3f3f, p.val);
}
clear(x);
for (edge p: to[x]) {
if (vis[p.to]) continue;
root = 0;
rootm = 0x3f3f3f3f;
tot = size[x];
getroot(p.to, 0x3f3f3f3f);
solve(root);
}
}
int main() {
scanf("%d%d", &n, &m);
int x, y, w;
for (int i = 1; i <= n-1; i++) {
scanf("%d%d%d", &x, &y, &w);
edge new1, new2;
new1.to = y;
new1.val = w;
to[x].push_back(new1);
new2.to = x;
new2.val = w;
to[y].push_back(new2);
}
for (int i = 1;i <= m;i++){
scanf("%d", &k[i]);
}
root = 0;
rootm = 0x3f3f3f3f;
tot = n;
getroot(1);
solve(root);
for (int i = 1; i <= m; i++) {
if (ans[i]) printf("AYE\n");
else printf("NAY\n");
}
return 0;
}
一定要记住树上点对只是点分治最简单的应用。