rt，巨佬救救我

#include<bits/stdc++.h>
using namespace std;

const int maxn=10010;

int n,m,rt,size[maxn],vis[maxn],max_part=1<<30,len[maxn],js,ans[maxn],size_part;
int ask[maxn],now[maxn],blo[maxn];
int ver[maxn<<1],head[maxn],nxt[maxn<<1],edge[maxn<<1],tot;
  
bool cmp(int x,int y)
{
	return len[x]<len[y];
}
  
void add(int u,int v,int w)
{
	ver[++tot]=v;
	nxt[tot]=head[u];
	head[u]=tot;
	edge[tot]=w;	
} 
  
void findrt(int x,int fa)
{
	size[x]=1;
	int maxp=0;
	for(int i=head[x];i;i=nxt[i])
	{
		int y=ver[i];
		if(y!=fa&&!vis[y])
		{
			findrt(y,x);
			size[x]+=size[y];
			maxp=max(maxp,size[y]);
		}
	}
	maxp=max(maxp,size_part-size[x]);
	if(maxp<max_part)
	{
		max_part=maxp;
		rt=x;
	}
}
  
void dis(int x,int fa,int dist,int from)
{
	len[x]=dist;now[++js]=x;blo[x]=from;
	for(int i=head[x];i;i=nxt[i])
	{
		int y=ver[i];
		if(y!=fa&&!vis[y]) dis(y,x,dist+edge[i],from);
	}
}
  
int calc(int x)
{
	js=1;
	now[1]=x;
	len[x]=0;
	blo[x]=x;
	for(int i=head[x];i;i=nxt[i])
	{
		int y=ver[i];
		if(!vis[y]) dis(y,x,edge[i],y);
	}
	sort(now+1,now+js+1,cmp);
	for(int i=1;i<=m;i++)
	{
		int l=1,r=js;
		if(!ans[i])
		{
			while(l<r)
			{
				int ll=now[l],rr=now[r];
				if(len[ll]+len[rr]<ask[i]) l++;
				else if(len[ll]+len[rr]>ask[i]) r--;
				else 
                {
                    if(blo[ll]==blo[rr])
					{
						if(blo[rr]==blo[now[r-1]]) r--;
						else l++;
					}
					else 
					{
						ans[i]=1;
						break;
					}
                }
			}
		} 
	}
}

void divide(int x)
{
	max_part=1<<30;
	findrt(x,0);
	vis[rt]=1;
	calc(rt);
	for(int i=head[rt];i;i=nxt[i])
	{
		int y=ver[i];
		if(!vis[y])
		{
			size_part=size[y];
			divide(y);
		}
	}
}
  
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<n;i++)
	{
		int x,y,z;
		scanf("%d %d %d",&x,&y,&z);
		add(x,y,z),add(y,x,z);
	}
	for(int i=1;i<=m;i++) 
    {
        scanf("%d",&ask[i]);
        if(ask[i]==0) ans[i]=1;
    }
	size_part=n;
	divide(1); 
	for(int i=1;i<=m;i++) 
	{
		if(ans[i]) printf("AYE\n");
		else printf("NAY\n");
	}
	return 0;
}