再次求助，调了好几天了……

TLE on #7,8,9

#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,d[10010],sz[10010],maxpart[10010],minn,minid,tot;
struct edge{int x,w;bool f;int cnt;};
vector<edge>v[10010],v2[10010];
int a[10010],cur,query[110];
int flag[10000010];
bool ans[110];
void dfs1(int x,int last,int tot)
{
    sz[x]=1,maxpart[x]=0;
    for(int i=0;i<v[x].size();i++)if(v[x][i].f)
        if(v[x][i].x!=last)
        {
            dfs1(v[x][i].x,x,tot);
            if(!last)v[x][i].cnt=sz[v[x][i].x];
            sz[x]+=sz[v[x][i].x];
            maxpart[x]=max(maxpart[x],sz[v[x][i].x]);
        }
    maxpart[x]=max(maxpart[x],tot-sz[x]);
    if(maxpart[x]<minn)minn=maxpart[x],minid=x;
}
int find(int x,int tot)
{
    minn=1e9,minid=0;
    dfs1(x,0,tot);
    return minid;
}
void dfs2(int x,int last,int id)
{
    //cout<<2<<" "<<x<<" "<<d[x]<<endl;
    if(d[x]>1e7)return;
    if(!flag[d[x]])
    {
        flag[d[x]]=id;
        a[++cur]=d[x];
    }
    for(int i=1;i<=m;i++)if(d[x]<=query[i])
        if(flag[query[i]-d[x]]<id&&flag[query[i]-d[x]]!=0||d[x]==query[i])
            ans[i]=1;
    for(int i=0;i<v[x].size();i++)
        if(v[x][i].x!=last)
        {
            d[v[x][i].x]=d[x]+v[x][i].w;
            dfs2(v[x][i].x,x,id);
        }
}
void solve(int x)
{
    //cout<<x<<" "<<ans[1]<<endl;
    //for(int i=0;i<v[x].size();i++)if(v[x][i].f)
        //cout<<v[x][i].w<<",";cout<<endl;
    memset(d,0,sizeof(d));
    for(int i=0;i<v[x].size();i++)if(v[x][i].f)
    {
        d[v[x][i].x]=v[x][i].w;
        dfs2(v[x][i].x,x,i+1);
    }
    for(int i=1;i<=cur;i++)
        flag[a[i]]=0;
    cur=0;
    v2[x]=v[x];
    for(int i=1;i<=n;i++)
        for(int j=0;j<v[i].size();j++)
            if(i==x||v[i][j].x==x)v[i][j].f=0;
    for(int i=0;i<v2[x].size();i++)if(v2[x][i].f)
        solve(find(v[x][i].x,v[x][i].cnt));
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++)
    {
        int x,y,w;
        scanf("%d%d%d",&x,&y,&w);
        v[x].push_back({y,w,1,0});
        v[y].push_back({x,w,1,0});
    }
    for(int i=1;i<=m;i++)scanf("%d",&query[i]);
    solve(find(1,n));
    for(int i=1;i<=m;i++)printf(ans[i]?"AYE\n":"NAY\n");
    return 0;
}