思想
点分治的思想其实就是在树上进行分治。从而降低复杂度。
每次找到一个点，对其进行处理，然后删除这个点，对剩下的子树进行递归处理。
因为重心的每个儿子的大小不超过(frac{n}{2})，所以如果这个点是重心的话，就可保证递归层数最多为log层。
实现
在弄懂点分治思想的情况下，点分治的代码还是比较好写的。虽然码量不小，但是思路比较显然。细节较多。
有时候重心会比较难找(或者懒得找重心)，可以(rand)一个点作为根。出题人一般不会卡掉的。
例题
思路
点分治的模板题。对于当前的树，统计出当前每个点到根的距离，然后看是否有两个距离相加为K。注意在同一棵子树中的点是不行的。所以应该处理一下。方法有很多。我是将之前子树的距离和当前子树的距离分开。然后用双指针去拼K。
如果递归m次可能会无法承受。所以可以在每次递归的时候都统计一下每个询问的答案。
这个题数据可能比较水，没有找重心一样能过去
代码
/*
* @Author: wxyww
* @Date: 2019-01-30 08:05:27
* @Last Modified time: 2019-01-30 09:41:38
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<bitset>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 10010;
ll read() {
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
int n,m;
struct node {
int v,nxt,w;
}e[N << 1];
int que[N],ans[N];
int head[N],ejs;
void add(int u,int v,int w) {
e[++ejs].v = v;e[ejs].nxt = head[u];head[u] = ejs;e[ejs].w = w;
}
int rt;
int dis[N],js;
void dfs(int u,int father,int dist) {
dis[++js] = dist;
for(int i = head[u];i;i = e[i].nxt) {
int v = e[i].v;if(v == father) continue;
dfs(v,u,dist + e[i].w);
}
}
void solve(int u,int father) {
int rt = u;
int now = 0;js = 0;
for(int i = head[rt];i;i = e[i].nxt) {
int v = e[i].v;if(v == father) continue;
dfs(v,u,e[i].w);
sort(dis + 1,dis + now + 1);sort(dis + now + 1,dis + js + 1);
for(int i = 1;i <= m;++i) {
int l = 0,r = js;
while(l <= now && r > now) {
while(dis[l] + dis[r] < que[i] && l <= now && r > now) ++l;
while(dis[l] + dis[r] > que[i] && l <= now && r > now) --r;
if(dis[l] + dis[r] == que[i] && l <= now && r > now) {
ans[i] = 1;break;
}
}
}
now = js;
}
for(int i = head[rt];i;i = e[i].nxt) {
int v = e[i].v;if(v == father) continue;
solve(v,rt);
}
}
int main() {
n = read();m = read();
for(int i = 1;i < n;++i) {
int u = read(),v = read(),w = read();
add(u,v,w);add(v,u,w);
}
for(int i = 1;i <= m;++i) que[i] = read();
solve(1,0);
for(int i = 1;i <= m;++i) {
if(ans[i]) puts("AYE");
else puts("NAY");
}
return 0;
}