题目描述
给定一棵有n个点的树

询问树上距离为k的点对是否存在。

输入格式
n,m 接下来n-1条边a,b,c描述a到b有一条长度为c的路径

接下来m行每行询问一个K

输出格式
对于每个K每行输出一个答案，存在输出“AYE”,否则输出”NAY”(不包含引号)

输入输出样例
输入 #1复制
2 1
1 2 2
2
输出 #1复制
AYE

说明/提示
对于30%的数据n<=100

对于60%的数据n<=1000,m<=50

对于100%的数据n<=10000,m<=100,c<=10000,K<=10000000

因为数据比较大，故不能树形dp，所以我们需要点分治来解决。

每次取重心分治，分为经过根和不经过根的路径。然后处理经过根的路径即可。

每次分治，因为我们取树的重心，所以分治 log 层 。 每次处理经过根的答案复杂度O(n) 。

总复杂度 n * log(n) * 大常数 * m。 因为当值太大时无法数组标记，但是本题可以。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+10,inf=0x3f3f3f3f;
int n,m,k[N],res[N],rt,sz[N],vis[N],sum,st[N],dis[N],cnt,mx;
int head[N],nex[N<<1],to[N<<1],w[N<<1],tot;
unordered_map<int,int> mp;
inline void add(int a,int b,int c){to[++tot]=b; nex[tot]=head[a]; w[tot]=c; head[a]=tot;}
void get(int x,int fa){
	sz[x]=1; int mxp=0;
	for(int i=head[x];i;i=nex[i]){
		if(to[i]==fa||vis[to[i]])	continue;
		get(to[i],x);	sz[x]+=sz[to[i]]; mxp=max(mxp,sz[to[i]]);
	}
	mxp=max(mxp,sum-sz[x]);	if(mxp<mx) mx=mxp,rt=x;
}
void getdis(int x,int fa){
	st[++cnt]=dis[x];
	for(int i=head[x];i;i=nex[i]){
		if(to[i]==fa||vis[to[i]])	continue;
		dis[to[i]]=w[i]+dis[x]; getdis(to[i],x);
	}
}
void solve(int x){
	for(int i=head[x];i;i=nex[i]){
		if(vis[to[i]])	continue;
		cnt=0; dis[to[i]]=w[i]; getdis(to[i],x);
		for(int j=1;j<=cnt;j++)
			for(int s=1;s<=m;s++)
				if(k[s]>=st[j])	res[s]|=mp[k[s]-st[j]];
		for(int j=1;j<=cnt;j++)	mp[st[j]]=1;
	}
	mp.clear();
}
void divide(int x){
	vis[x]=1;	mp[0]=1;	solve(x);
	for(int i=head[x];i;i=nex[i]){
		if(vis[to[i]])	continue;
		sum=sz[to[i]]; mx=inf,rt=0;
		get(to[i],0); get(rt,0); divide(rt);
	}
}
signed main(){
	cin>>n>>m;
	for(int i=1,a,b,c;i<n;i++)	scanf("%d %d %d",&a,&b,&c),add(a,b,c),add(b,a,c);
	for(int i=1;i<=m;i++)	cin>>k[i];
	mx=sum=n; get(1,0);	get(rt,0);	divide(rt);
	for(int i=1;i<=m;i++)	puts(res[i]?"AYE":"NAY");
	return 0;
}