求助淀粉质

TLE on #7 & #9

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout)
#define dbout cerr<<"[DeBug]:"
#define mem(x,y) memset(x,y,sizeof(x))
inline int read()
{
    int x(0),f(1);char c=getchar();
    while(c>'9'||c<'0')f=c=='-'?-1:1,c=getchar();
    while(c>='0'&&c<='9')x=x*10+c-48,c=getchar();
    return f*x;
}
const int N=10010,Q=110;
struct edge
{
    int to,val;
    edge(int To=0,int Val=0){to=To;val=Val;}
};
vector<edge>G[N];int n,m;int que[Q];bool ans[Q];
void add(int x,int y,int z){G[x].push_back(edge(y,z));G[y].push_back(edge(x,z));}
int sz[N],mx[N],root=0,sum;bool vis[N];
int tot,dis[N];
void gtdis(int x,int fa,int len)
{
    dis[++tot]=len;
    for(auto y:G[x])if(y.to!=fa&&(!vis[y.to])&&len+y.val<=10000000)
    gtdis(y.to,x,len+y.val);
}
int clr[N];bool qwq[100000010];
void calc(int x)
{
    int nw=0;
    for(auto y:G[x])if(!vis[y.to])
    {
        tot=0;gtdis(y.to,x,y.val);
        for(int i=1;i<=tot;i++)for(int j=1;j<=m;j++)
        if(que[j]>=dis[i]&&qwq[que[j]-dis[i]])ans[j]=1;
        for(int i=1;i<=tot;i++)clr[++nw]=dis[i],qwq[dis[i]]=1;
    }
    for(int i=1;i<=nw;i++)qwq[clr[i]]=0;
}
void gtrt(int x,int fa)
{
    sz[x]=1;mx[x]=0;
    for(auto y:G[x])if(y.to!=fa&&(!vis[y.to]))
    {
        gtrt(y.to,x);
        mx[x]=max(mx[x],sz[y.to]);sz[x]+=sz[y.to];
    }
    mx[x]=max(mx[x],sum-sz[x]);
    if(mx[x]<mx[root])root=x;
}
void dfs(int x)
{
    vis[x]=qwq[0]=1;calc(x);
    for(auto y:G[x])if(!vis[y.to])
    {
        sum=sz[y.to];root=0;gtrt(y.to,x);
        dfs(y.to);
    }
}
int main()
{
    //fr();
    n=read();m=read();
    for(int i=1;i<n;i++){int x=read(),y=read(),z=read();add(x,y,z);}
    for(int i=1;i<=m;i++)que[i]=read();
    mx[0]=INT_MAX;sum=n;gtrt(1,0);
    dfs(root);
    for(int i=1;i<=m;i++)
    puts(ans[i]?"AYE":"NAY"); 
    return 0;
}