求助 60Pts

记录:
https://www.luogu.org/recordnew/show/15286153

#include<cstdio>
#include<cstring>
#include<cmath>
#include<climits>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<complex>
#include<iostream>
#include<map>
#include<queue>
#include<vector>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
struct edge
{
    int to,next,weight;
}a[200020];
int head[100010];
int maxp[100010];
int size[100010];
int dist[100010];
int rem[100010];
int query[10000010];
int judge[100010];
int q[100010];
int ans[10000010];
int cnt(0),sum(0);
int n,m,root(0);
int vis[100010];
void addedge(int xi,int yi,int wi)
{
    a[cnt].to=yi;
    a[cnt].next=head[xi];
    a[cnt].weight=wi;
    head[xi]=cnt++;
}
void dfs1(int u,int fa)
{
    size[u]=1;maxp[u]=0;
    for(int i=head[u];i!=-1;i=a[i].next)
    {
        int v=a[i].to;
        if(v==fa||vis[v])continue;
        dfs1(v,u);
        size[u]+=size[v];
        maxp[u]=max(maxp[u],size[v]);
    }
    maxp[u]=max(maxp[u],sum-size[u]);
    if(maxp[u]<maxp[root])root=u;
}
void dfs2(int u,int fa)
{
    rem[++rem[0]]=dist[u];
    for(int i=head[u];i!=-1;i=a[i].next)
    {
        int v=a[i].next;
        if(v==fa||vis[v])continue;
        dist[v]=dist[u]+a[i].weight;
        dfs2(v,u);
    }
}
void cal(int u)
{
    int p(0);
    for(int i=head[u];i!=-1;i=a[i].next)
    {
        int v=a[i].to;if(vis[v])continue;
        rem[0]=0;dist[v]=a[i].weight;dfs2(v,u);
        for(int j=rem[0];j;j--)for(int k=1;k<=m;k++)if(query[k]>=rem[j])ans[k]|=judge[query[k]-rem[j]];
        for(int j=rem[0];j;j--){q[++p]=rem[j];judge[rem[j]]=1;}
    }
    for(int i=1;i<=p;i++)judge[q[i]]=0;
}
void dfs3(int u)
{
    vis[u]=judge[0]=1;cal(u);
    for(int i=head[u];i!=-1;i=a[i].next)
    {
        int v=a[i].to;
        if(vis[v])continue;
        sum=size[v];maxp[root=0]=INF;
        dfs1(v,0);dfs3(root);
    }
}
int main()
{
    memset(head,-1,sizeof(head));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n-1;i++)
    {
        int u,v,w;scanf("%d%d%d",&u,&v,&w);
        addedge(u,v,w);addedge(v,u,w);
    }
    for(int i=1;i<=m;i++)scanf("%d",&query[i]);
    maxp[root]=sum=n;
    dfs1(1,0);dfs3(root);
    for(int i=1;i<=m;i++)printf((ans[i])?"AYE\n":"NAY\n");
    return 0;
}