如题

#include<bits/stdc++.h>
#define maxn 10001
#define maxk 10000010
using namespace std;
vector<pair<int,int> >edge[maxn<<1];
bool vis[maxn];
int maxpt[maxn];
int siz[maxn];
int rt,rn;
bool judge[maxk];
int dis[maxn];
int tmp[maxn];
int q[maxn];
int n,m;
void getrt(int p,int fa)
{
	maxpt[p]=0;
	siz[p]=1;
	int l=edge[p].size(),v;
	for(int i=0;i<l;i++)
	{
		v=edge[p][i].first;
		if(v==fa||vis[v])
			continue;
		getrt(v,p);
		siz[p]+=siz[v];
		maxpt[p]=max(maxpt[p],siz[v]);
	}
	maxpt[p]=max(rn-siz[p],maxpt[p]);
	if(maxpt[p]<maxpt[rt])rt=p;
}
int cnt;
int getdis(int p,int fa)
{
	tmp[++cnt]=dis[p];
	int l=edge[p].size();
	for(int i=0;i<l;i++)
	{
		int v=edge[p][i].first;
		if(v==fa||vis[v])
			continue;
		dis[v]=dis[p]+edge[p][i].second;
		getdis(v,p);
	}
}
bool ans[maxn];
int solve(int u)
{
	queue<int>qu;
	int l=edge[u].size();
	for(int i=0;i<l;i++)
	{
		int v=edge[u][i].first;
		int w=edge[u][i].second;
		cnt=0;
		dis[v]=w;
		getdis(v,u);//处理以u为根节点的距离 
		for(int j=1;j<=cnt;j++)
			for(int k=1;k<=m;k++)
				if(q[k]>=tmp[j])
					ans[k]|=judge[q[k]-tmp[j]];
		for(int j=1;j<=cnt;j++)
		{
			qu.push(tmp[j]);
			judge[tmp[j]]=true;
		}
	}
	while(!qu.empty())
	{
		judge[qu.front()]=false;
		qu.pop();
	}
}
void divide(int p)
{
	judge[0]=true;
	vis[p]=1;
	solve(p);
	int l=edge[p].size();
	for(int i=0;i<l;i++)
	{
		int v=edge[p][i].first;
		if(vis[v])
			continue;
		rt=0;
		maxpt[rt]=rn=siz[v]; 
		getrt(v,0);
		getrt(rt,0);
		divide(rt);
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	int u,v,w;
	for(int i=1;i<n;i++)
	{
		scanf("%d%d%d",&u,&v,&w);
		edge[u].push_back(make_pair(v,w));
		edge[v].push_back(make_pair(u,w));
	}
	for(int i=1;i<=m;i++)
		scanf("%d",&q[i]);
	maxpt[0]=rn=n;
	getrt(1,0);
	getrt(rt,0);
	divide(rt);
	for(int i=1;i<=m;i++)
		if(ans[i])cout<<"AYE\n";
		else cout<<"NAY\n";
		//cout<<(ans[i]?"AYE":"NAY")<<"\n";
	return 0;
}