萌新刚学点分治，求助

评测记录

#include <bits/stdc++.h>
using namespace std;
const int maxN = 1e5+10;
const int inf  = 1e7+10;
const int maxK = 1e7+10;
int N,M;
int head[maxN],cnt,q[maxN],ans[maxN];
struct qxx{int next,to,w;}edge[maxN<<1];
void add(int u,int v,int w)
{
    cnt++;
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    edge[cnt].w=w;
    head[u]=cnt;
}
int visit[maxN],siz[maxN],mx[maxN],zx,sum;
void getzx(int u,int fa)
{
    //cout<<"RT: "<<u<<endl;
    siz[u]=1,mx[u]=0;
    for(int i=head[u];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(v==fa||visit[v])continue;
        getzx(v,u);
        siz[u]+=siz[v];
        mx[u]=max(mx[u],siz[v]);
        //cout<<"size "<<u<<" "<<siz[u]<<endl;
    }
    mx[u]=max(mx[u],sum-siz[u]);
    //cout<<"max "<<u<<" "<<mx[u]<<endl;
    if(mx[u]<mx[zx])zx=u;
    //cout<<"zx "<<zx<<endl;
    //cout<<"OVER "<<u<<endl;
}
int dist[maxN],temp[maxN];
void getdist(int u,int fa)
{
    temp[++temp[0]]=dist[u];
    for(int i=head[u];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(v==fa||visit[v])continue;
        dist[v]=dist[u]+edge[i].w;
        getdist(v,u);
    }
}
int cl[maxN],flag[maxK];
void cal(int u)
{
    //cout<<"CAL: "<<u<<endl;
    int l=0;
    for(int i=head[u];i;i=edge[i].next)
    {
        int v=edge[i].to;
        //cout<<v<<endl;
        if(visit[v])continue;
        //cout<<v<<" ok\n";
        temp[0]=0;
        dist[v]=edge[i].w;
        getdist(v,u);
        //for(int i=0;i<=3;i++)cout<<flag[i]<<" ";
        //cout<<endl;
        for(int j=1;j<=temp[0];j++)
        {
            for(int k=1;k<=M;k++)
            {
                //cout<<q[k]<<" "<<temp[j]<<endl;
                if(q[k]>=temp[j]&&flag[q[k]-temp[j]])ans[k]=1;
            }
        }
        for(int j=1;j<=temp[0];j++)flag[temp[j]]=1,cl[++l]=temp[j];
    }
    for(int i=1;i<=l;i++)flag[cl[i]]=0;
}
void divide(int u)
{
    visit[u]=flag[0]=1;
    cal(u);
    for(int i=head[u];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(visit[v])continue;
        sum=siz[v];mx[zx=0]=inf;
        getzx(v,0);
        divide(v);
    }
}
int main()
{
    scanf("%d%d",&N,&M);
    for(int i=1;i<N;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
    }
    for(int i=1;i<=M;i++)scanf("%d",&q[i]);
    mx[zx=0]=sum=N;
    getzx(1,0);
    divide(zx);
    for(int i=1;i<=M;i++)
    {
        if(ans[i])printf("AYE\n");
        else printf("NAY\n");
    }
    return 0;
}