点分治 - 知识点梳理

分治是一种将大的问题拆分成更小的问题并分而治之的算法，有利于使一个大的问题迅速缩小。在线性区间上的分治一般从区间中点将区间一分为二（这个中点也叫做分治中心），这样分 \(\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;
}

一定要记住树上点对只是点分治最简单的应用。