rt，TLE on #7 #9，已经交了一页了

题目传送门

各数组的解释： siz[i]:以i为根的子树大小

maxx[i]:以i为根的子树大小最大值

dist[i]:节点i到根节点的距离

dd[i]:存储求出的所有距离 dd[++cnt]=dist[u]

ques[i]：第i个询问

ok[i]:是否存在长度为i的路径

ret[i]:第i个询问的答案

vis[i]:节点i是否被访问

rec:vector 存储需要被复原的ok数组的下标

g,w:vector 存图（改成链式前向星好像仍然TLE）

#include<bits/stdc++.h>
using namespace std;
const int N=2e4+5,inf=1e7+1;
int n,q,rt,cnt,all;
int siz[N],maxx[N],dist[N],dd[N],ques[N];
bool ok[inf],ret[N],vis[N];
vector<int> g[N],w[N],rec;
void get_cog(int u,int las)//求重心
{
	siz[u]=1; maxx[u]=0;
	for(int i=0;i<g[u].size();i++)
	{
		int v=g[u][i];
		if(v==las||vis[v])continue;
		get_cog(v,u);
		maxx[u]=max(maxx[u],siz[v]);
		siz[u]+=siz[v];
	}
	maxx[u]=max(maxx[u],all-siz[u]);
	if(maxx[u]<=all/2) rt=u;
}
void get_dist(int u,int las)//求dist数组
{
	dd[++cnt]=dist[u];
	for(int i=0;i<g[u].size();i++)
	{
		int v=g[u][i];
		if(v==las||vis[v])continue;
		dist[v]=dist[u]+w[u][i];
		get_dist(v,u);
	}
}
void calc(int u)
{
	ok[0]=vis[u]=1;
	rec.push_back(0); 
	for(int i=0;i<g[u].size();i++)
	{
		int v=g[u][i];
		if(vis[v]) continue;
		dist[v]=w[u][i];
		get_dist(v,u); 
		for(int j=1;j<=cnt;j++)//更新答案
			for(int k=1;k<=q;k++)
				if(ques[k]>=dd[j])
					ret[k]|=ok[ques[k]-dd[j]];
		for(int j=1;j<=cnt;j++)//标记存在路径
			if(dd[j]<inf) rec.push_back(dd[j]),ok[dd[j]]=1;
		cnt=0;
	}
	for(int i=0;i<rec.size();i++) ok[rec[i]]=0; //复原
	rec.clear();
	for(int i=0;i<g[u].size();i++)
	{
		int v=g[u][i];
		if(vis[v]) continue;
		rt=0;
		all=siz[v];
		get_cog(v,u);//求子树的重心
		get_cog(rt,0);//重算子树大小
		calc(v);
	}
}
int main()
{
	scanf("%d%d",&n,&q);
	int x,y,z;
	for(int i=1;i<n;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		g[x].push_back(y); g[y].push_back(x);
		w[x].push_back(z); w[y].push_back(z);
	}
	for(int i=1;i<=q;i++)
		scanf("%d",&ques[i]);
	maxx[0]=n; all=n;
	get_cog(1,0);
	get_cog(rt,0);//重计子树大小 
	calc(rt);
	for(int i=1;i<=q;i++)
		if(ret[i]) puts("AYE");
		else puts("NAY");
}