萌新求助点分治

RT，应该是复杂度假了

#include<stdio.h>
#include<algorithm>
#include<iostream>
using namespace std;
const int MAXN=1e4+10,MAXK=1e7+10,INF=1e9+7;
int n,m,k[MAXN],to[MAXN],nxt[MAXN],head[MAXN],val[MAXN],cnt;
int siz[MAXN],MIN,node,c[MAXN],tot,q[MAXN],TOT;bool b[MAXK],vis[MAXN],B[MAXN];
void add(int x,int y,int v)
{
    to[++cnt]=y,nxt[cnt]=head[x];
    head[x]=cnt,val[cnt]=v;return ;
}
void bal(int x,int fa,int sum)
{
    int MAX=0;siz[x]=1;
    for(register int i=head[x];i;i=nxt[i])
    {
        int y=to[i];if(y==fa||vis[y]) continue;
        bal(y,x,sum),siz[x]+=siz[y],MAX=max(MAX,siz[y]);
    }
    MAX=max(MAX,sum-siz[x]);
    if(MAX<MIN) MIN=MAX,node=x;
    return ;
}
void calc(int x,int fa,int dis)
{
    if(dis>1e7) return ;
    for(register int i=1;i<=m;++i) if(k[i]>=dis&&b[k[i]-dis]) B[i]=true;
    c[++tot]=dis,q[++TOT]=dis;
    for(register int i=head[x];i;i=nxt[i])
    {
        int y=to[i];if(y==fa||vis[y]) continue;
        calc(y,x,dis+val[i]);
    }
    return ;
}
void solve(int x)
{
    b[0]=1,TOT=0;vis[x]=true;
    for(register int i=head[x];i;i=nxt[i])
    {
        int y=to[i];if(vis[y]) continue;
        tot=0,calc(y,x,val[i]);
        for(register int i=1;i<=tot;++i) b[c[i]]=true;
    }
    for(register int i=1;i<=TOT;++i) b[q[i]]=false;
    for(register int i=head[x];i;i=nxt[i])
    {
        int y=to[i];if(vis[y]) continue;
        MIN=INF,bal(y,0,siz[y]);solve(node);
    }
    return ;
}
int main()
{
    cin>>n>>m;
    for(register int i=1;i<n;++i)
    {
        int u,v,w;cin>>u>>v>>w;
        add(u,v,w),add(v,u,w);
    }
    for(register int i=1;i<=m;++i) cin>>k[i];
    MIN=INF;bal(1,0,n);solve(node);
    for(register int i=1;i<=m;++i) (B[i])?cout<<"AYE\n":cout<<"NAY\n";
}