TLE #8 求助

RT

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=10005,K=10000005,M=105;
int n,m,U,V,W,q[M],siz[N],root,ma[N],LEN,t,cnt,tot;
bool can[M],Vis[N];
int head[N],to[N<<1],dis[N<<1],nxt[N<<1],cnt2;//lsqxx
struct rec
{
    int len,tr;
    bool operator<(const rec B)const
    {
        return len<B.len;
    }
}v[N];
#ifndef ONLINE_JUDGE
double st,et,st1,et1,sum;
#endif
void add(int From,int To,int Dis)
{
    to[++cnt2]=To,dis[cnt2]=Dis,nxt[cnt2]=head[From],head[From]=cnt2;
}
void froot(int now,int fa)
{
    siz[now]=1,ma[now]=0;
    for(int i=head[now];i;i=nxt[i])
        if((t=to[i])!=fa&&!Vis[t])
        {
            froot(t,now);
            siz[now]+=siz[t],ma[now]=max(ma[now],siz[t]);
        }
    ma[now]=max(ma[now],LEN-siz[now]);
    if(!root||ma[now]<ma[root])root=now;
}
void dfs(int now,int fa,int len,int Tr)
{
    v[++cnt]=rec{len,Tr};
    for(int i=head[now];i;i=nxt[i])
        if((t=to[i])!=fa&&!Vis[t])
            dfs(t,now,len+dis[i],Tr);
}
void sol(int Root)
{
    v[cnt=1]=rec{0,0};
    for(int i=head[Root];i;i=nxt[i])
        if(!Vis[t=to[i]])
            dfs(t,Root,dis[i],t);
    //cout<<cnt<<endl;
    tot+=cnt;
    //st1=clock();
    sort(v+1,v+cnt+1);
    int l,r;
    for(int i=1;i<=m;i++)
    {
        if(can[i])continue;
        l=1,r=cnt;
        while(l<r)
        {
            if(v[l].len+v[r].len<q[i])l++;
            else if(v[l].len+v[r].len>q[i])r--;
            else
            {
                if(v[l].tr!=v[r].tr)
                {
                    can[i]=1;
                    break;
                }
                else if(v[l].len==v[l+1].len)l++;
                else r--;
            }
        }
    }
    //et1=clock();
    //sum+=et1-st1;
}
void dfz(int Root)
{
    Vis[Root]=1;
    sol(Root);
    for(int i=head[Root];i;i=nxt[i])
        if(!Vis[t=to[i]])
        {
            //sol(t);
            LEN=siz[t],root=0;
            froot(t,0);
            //cout<<root<<endl;
            dfz(root);
        }
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("P3806_8.in","r",stdin);
freopen("my.txt","w",stdout);
st=clock();
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<n;i++)
    {
        cin>>U>>V>>W;
        //to[U].push_back(V),to[V].push_back(U),dis[U].\
        //push_back(W),dis[V].push_back(W);
        add(U,V,W);add(V,U,W);
    }
    for(int i=1;i<=m;i++)cin>>q[i];
    LEN=n;
    froot(1,0);
    dfz(root);
#ifndef ONLINE_JUDGE
et=clock();
cout<<"time:"<<et-st<<"ms"<<endl;
cout<<sum<<endl<<tot;
fclose(stdout);
#endif
    for(int i=1;i<=m;i++)cout<<(can[i]?"AYE":"NAY")<<endl;
    return 0;
}