rt，点分治求找出t的原因

400ms，但是题目要求200ms

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10,M=N*2,K=1e7+10;
int n,Q,m,qt,f[K]; 
int h[N],e[M],ne[M],idx;
ll w[M],q[N];
bool st[N];
void add(int a,int b,int c){
	e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
ll get_sz(int u,int fa){
	if(st[u]) return 0;
	int res=1;//子树大小初始为1别赋值成0了 
	for(int i=h[u];~i;i=ne[i]){
		int j=e[i];
		if(j==fa) continue;
		res+=get_sz(j,u);
	}
	return res;
}
void get_dist(int u,int fa,ll dis){
	if(st[u]) return;
	q[++qt]=dis;
	for(int i=h[u];~i;i=ne[i]){
		int j=e[i];
		if(j==fa)continue;
		get_dist(j,u,dis+w[i]);
	}
}
ll get_wc(int u,int fa,int tot,int &rt){
	if(st[u]) return 0;
	ll res=1,ans=0;
 	for(int i=h[u];~i;i=ne[i]){
		int j=e[i];
		if(j==fa)continue;
		ll t=get_wc(j,u,tot,rt);
		ans=max(ans,t);res+=t; 
	}
	ans=max(ans,tot-res);
	if(ans<=tot/2) rt=u;
	return res;
}

ll check(ll a[],int X){
	ll res=0;
	for(int i=1;i<=X;i++)
		if(a[i]<=m) f[a[i]]++;
	for(int i=1;i<=X;i++)
		if(a[i]<=m&&f[m-a[i]]){
			if(m-a[i]==a[i]) res+=f[a[i]]-1;
			else res+=f[m-a[i]];
		}
	for(int i=1;i<=X;i++) 
		if(a[i]<=m)f[a[i]]=0;
	return res;
}
ll p[N];
ll calc(int u){
	if(st[u]) return 0;
	int sz=get_wc(u,-1,get_sz(u,-1),u),pt=0;ll res=0;
	st[u]=1;
	for(int i=h[u];~i;i=ne[i]){
		int j=e[i];
		qt=0;
		get_dist(j,u,w[i]);
		res-=check(q,qt);
		for(int k=1;k<=qt;k++){
			p[++pt]=q[k];
			if(q[k]==m) res++;
		}
	}
	res+=check(p,pt);
	for(int i=h[u];~i;i=ne[i]) res+=calc(e[i]);
	return res; 
}
int main(){
	memset(h,-1,sizeof(h));
    scanf("%d%d",&n,&Q);
    for(int i=1;i<n;i++){
    	int a,b,c;scanf("%d%d%d",&a,&b,&c);
    	add(a,b,c);add(b,a,c);
	}
	while(Q--){
		memset(st,0,sizeof(st));
		scanf("%d",&m);
		int t=calc(1);
		printf(t?"AYE":"NAY");
		putchar('\n');
	}
    return 0;
}