1 概念

点分治是树分治的一种，主要用于处理树上路径问题。

注意这颗树不需要有根，即这是一颗无根树。

下面以例题分析点分治的基本思想。

2 基本思想

首先你需要会的前置知识：树的重心。

我们来看这样一道例题：【模板】点分治 ：

给出一颗无根树，有边权，询问树上是否存在距离为 \(k\) 的点。

首先会有显然的树上差分做法，不过太劣。

考虑这样一件事：对于树上的所有路径，可以分成两部分：

1. 经过当前根节点的。
2. 不经过当前根节点的。

对于第二种情况，他们一定在根节点的某个子树中。

我们发现，只要我们求出第一种情况对应的方案数，那么第二种情况就可以递归求解。

于是我们现在就有了点分治的初步思路：将路径分为经过与不经过根节点，对于后者继续递归分开求解。

但是如果直接随机取根节点求解，说不定会被卡成 \(O(n)\)（一条链）。此时就要提到上面强调的一个东西：由于原树是无根树，所有选择根节点的权利在于我们手里。我们只需要让他深度平衡，就可以保证复杂度为 \(O(\log n)\)。

那么如何让根节点平衡呢？这就要用到前置知识了：对于每一颗子树，让他的重心成为当前根节点就可以保证平衡。

所以我们总结一下点分治的基本步骤：

1. 找出当前子树的重心。
2. 根据题意对于当前子树的答案进行统计。
3. 分治各个子树，重复步骤 \(1\)。

这就是点分治的基本思想了。

接下来就是代码了。

3 代码

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int Maxn = 2e5 + 5;
const int Maxm = 1e7 + 5;

int n, m;
int head[Maxn], edgenum;
struct node {
	int nxt, to, w;
}edge[Maxn];

void add(int from, int to, int w) {
	edge[++edgenum] = {head[from], to, w};
	head[from] = edgenum;
}

int q[Maxn];
bool ok[Maxm];

struct pdac {
	bool del[Maxn];
	int siz[Maxn], cen, sum;
	void getcen(int x, int fa) {//求重心
		siz[x] = 1;
		int s = 0;
		for(int i = head[x]; i; i = edge[i].nxt) {
			int to = edge[i].to;
			if(del[to] || to == fa) continue;
			getcen(to, x);
			siz[x] += siz[to];
			s = max(s, siz[to]);
		}
		s = max(s, sum - siz[x]);
		if(s <= sum / 2) cen = x;
	}
	int dis[Maxn], cnt, d[Maxn];
	void getdis(int x, int fa) {//求当前子树各个节点到根节点的距离
		dis[++cnt] = d[x];
		for(int i = head[x]; i; i = edge[i].nxt) {
			int to = edge[i].to;
			if(del[to] || to == fa) continue;
			d[to] = d[x] + edge[i].w;
			getdis(to, x);
		}
	}
	bool vis[Maxm];
	int p[Maxn], tot;
	void dfs(int x) {//点分治
		del[x] = 1;
		vis[0] = 1;
		tot = 0;
		for(int i = head[x]; i; i = edge[i].nxt) {
			int to = edge[i].to;
			if(del[to]) continue;
			cnt = 0, d[to] = edge[i].w;
			getdis(to, x);
			for(int j = 1; j <= cnt; j++) {
				for(int k = 1; k <= m; k++) {
					if(q[k] >= dis[j]) {
						ok[k] |= vis[q[k] - dis[j]];//能否拆分 q[k]
					}
				}
			}
			for(int j = 1; j <= cnt; j++) {
				if(dis[j] >= Maxm) continue;//注意距离可能大于 k 的最大值，此时我们不需要存储，否则会 RE
				p[++tot] = dis[j];
				vis[dis[j]] = 1;
			}
		}
		for(int i = 1; i <= tot; i++) {//不要用 memset，会 TLE
			vis[p[i]] = 0;
		}
        //上：处理当前点信息
        //下：分治求解
		for(int i = head[x]; i; i = edge[i].nxt) {
			int to = edge[i].to;
			if(del[to]) continue;
			sum = siz[to];
			getcen(to, 0);
			getcen(cen, 0);//跑两边，求出以重心为根各个子树的大小
			dfs(cen);
		}
	}
	void solve() {
		sum = n;
		getcen(1, 0);
		getcen(cen, 0);//同理，跑两边
		dfs(cen);
		for(int i = 1; i <= m; i++) {
			if(ok[i]) {
				cout << "AYE\n";
			}
			else {
				cout << "NAY\n";
			}
		}
	}
}T;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(int i = 1; i < n; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		add(u, v, w), add(v, u, w);
	}
	for(int i = 1; i <= m; i++) {
		cin >> q[i];
	}
	T.solve();
	return 0;
}