淀粉汁代码玄关求条

#include<cstdio>
#include<vector>
#include<algorithm>
#define QwQ return 0
using namespace std;
const int N=1e5+50;
struct ed{int v,w;};
vector<ed>e[N];
int root,dep[N],f[N],size[N],n,k,m,que[N],S,tot,len[N];
bool vis[N],ans[10000150];
void getroot(int u,int fa){
	f[u]=0,size[u]=1;
	for(auto x:e[u]){
		int v=x.v;
		if(vis[v]||v==fa)continue;
		getroot(v,u);
		size[u]+=size[v];
		f[u]=max(f[u],size[v]);
	}
	f[u]=max(f[u],S-size[u]);
	if(f[u]<f[root])root=u;
}
void getdep(int u,int fa){
	for(auto x:e[u]){
		int v=x.v,w=x.w;
		if(v==fa||vis[v])continue;
		dep[v]=dep[u]+w;
		len[++tot]=dep[v];
		ans[len[tot]]=1;
		getdep(v,u);
	}
}
void getans(int u){
	dep[u]=0;
	tot=0;
	getdep(u,0);
	for(int i=1;i<=tot;i++){
		if(i+1>tot)break;
		for(int j=i+1;j<=tot;j++){
			if(len[i]+len[j]<=10000000)ans[len[i]+len[j]]=1;
		}
	}
}
void sol(int u){
	vis[u]=1;
	getans(u);
	for(auto x:e[u]){
		int v=x.v;
		if(vis[v])continue;
		S=size[v];
		root=0,f[v]=N;
		getroot(v,u);
		sol(root);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1,cu,cv,cw;i<n;i++){
		scanf("%d%d%d",&cu,&cv,&cw);
		e[cu].push_back({cv,cw});
		e[cv].push_back({cu,cw});
	}
	for(int i=1;i<=m;i++){
		scanf("%d",&k);
		que[i]=k;
	}
	f[0]=N,S=n;
	getroot(1,0);
	sol(root);
	for(int i=1;i<=m;i++){
		if(ans[que[i]])printf("AYE\n");
		else printf("NAY\n");
	}
	QwQ;
}