这道题确实可以优化，上述代码中相当于对于每一个询问都建一遍树，这样增加了时间复杂度。我们可以之间一遍树，将询问和每个询问的结果都存起来，在getans时统一处理，这样就实现了优化，可以AC。代码如下：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=10005;
const int INF=10000005;
int k;
int h[40010],e[40010],ne[40010],w[40010],idx;
int use[20010];
int d[20010],dis[N];
int f[20010],siz[20010];
int dep[10010];
int cnt,Siz,rt=1;
int ans[N];
int mx=1e9+7;
int n,m;
int ask[N];
void add(const int &a,const int &b,const int &c)
{
w[idx]=c,e[idx]=b,ne[idx]=h[a],h[a]=idx++;
w[idx]=c,e[idx]=a,ne[idx]=h[b],h[b]=idx++;
}
//求重心
void getroot(int u,int fa)//x为当前点，fa为父亲节点
{
f[u]=0,siz[u]=1;//f表示这个点最大子树的大小，siz是这个点子树大小的和
for(int i=h[u];i!=-1;i=ne[i])//枚举儿子
{
int y=e[i];
if(use[y]||y==fa) continue;//use表示之前遍历过了，这里没啥用
getroot(y,u);//往下遍历
siz[u]+=siz[y];
f[u]=max(f[u],siz[y]);//更新f
}
f[u]=max(f[u],Siz-siz[u]);//Siz表示在现在这棵子树中点的总数，开始时Siz=n，除了枚举的儿子所在的子树外，还有一棵子树是上面的那一堆，容斥原理
if(f[u]<mx)
{
mx=f[u];
rt=u;//更新root
}
}
//求到重心的距离
void getd(int x,int fa)
{
dis[++cnt]=d[x];
// printf("d[x]=%d,cnt=%d,dis[cnt]=%d\n",d[x],cnt,dis[cnt]);
//printf("dis[1]=%d dis[2]=%d\n",dis[1],dis[2]);
for(int i=h[x];i!=-1;i=ne[i])
{
int j=e[i];
if(j==fa||use[j]) continue;
d[j]=d[x]+w[i];
getd(j,x);
}
}
//求答案
void getans(const int &x,int w,const int sign)
{
cnt=0;
d[x]=w;
getd(x,0);
sort(dis+1,dis+1+cnt);
for(int i=1;i<=m;i++)
{
int l=1,r=cnt;
while(l<r)
{
if(dis[l]+dis[r]<=ask[i])
{
//printf("dis[1]=%d dis[2]=%d l=%d r=%d\n",dis[1],dis[2],l,r);
//printf("dis[l]=%d dis[r]=%d l+r%=d",dis[l],dis[r],dis[l]+dis[r]);
if(dis[l]+dis[r]==ask[i]) ans[i] += sign;
++l;
}
else --r;
}
}
}
//分治划分
void fz(const int &x)//x就是树根
{
//cout<<"x:"<<x<<endl;
use[x]=1;
getans(x,0,1);//
//printf("x=%d,ans1=%d\n",x,ans);
for(int i=h[x];i!=-1;i=ne[i])
{
int j=e[i];
if(use[j]) continue;
getans(j,w[i],-1);
// printf("x=%d,ans2=%d\n",x,ans);
Siz=siz[j],mx=1e9+7;
getroot(j,x);//找子树中的重心
// printf("%d kid-ans %d",x,rt);
// rts[j]=rt;
fz(rt);
}
}
signed main()
{
f[0]=1e9+7;
memset(h,-1,sizeof h);
scanf("%d%d",&n,&m);
for(int i=0;i<n-1;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
/*for(int i=1;i<=n;i++)
{
printf("%d:",i);
for(int j=h[i];j!=-1;j=ne[j]) printf("%d ",e[j]);
printf("\n");
}*/
Siz=n;
getroot(1,1);
//for(int i=1;i<=n;i++) cout<<i<<" f:"<<f[i]<<" siz:"<<siz[i]<<endl;
//cout<<"rt:"<<rt<<endl;
int root=rt;
for(int i=0;i<=n;i++)use[i]=0;
for(int i=1;i<=m;i++)
{
scanf("%d",&ask[i]);
//memset(use,0,sizeof use);
}
fz(root);
for(int i=1;i<=m;i++)
{
if(ans[i]>0) printf("AYE\n");
else printf("NAY\n");
}
}
```
by s_computer @ 2023-10-28 14:24:20