点分治板子求调，subtask3全RE

RT

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e4+5,maxm=100+5;

int n,m,k,idx=0,head[maxn],root=0,siz[maxn],rtSon=1e9;
int dis[maxn],disi;
bool ans[10000007],vis[maxn];
vector<int>ok;
struct edge {
    int u,v,w,next;
}e[maxn];

inline void Add(const int& u,const int& v,const int& w) {
    e[++idx]={u,v,w,head[u]};
    head[u]=idx;
    return ;
}

void find_root(int now,int father,int tot) {
    int Son=0;
    siz[now]=1;
    for(int i=head[now];i;i=e[i].next) {
        int son=e[i].v;
        if(son==father||vis[son]) continue;
        find_root(son,now,tot);
        if(siz[son]>Son) Son=siz[son];
        siz[now]+=siz[son];
    }
    if(tot-siz[now]>Son) Son=tot-siz[now];
    if(Son<rtSon) root=now,rtSon=siz[Son];
    return ;
}

void get_dis(int now,int father,int distance) {
    dis[++disi]=distance;
    siz[now]=1;
    for(int i=head[now];i;i=e[i].next) {
        int son=e[i].v;
        if(son==father||vis[son]) continue;
        get_dis(son,now,distance+e[i].w);
        siz[now]+=siz[son];
    }
    return ;
}

void solve(int now,int father,int tot) {
    rtSon=1e9;
    find_root(now,father,tot);
    dis[1]=0;
    vis[root]=true;
    ok.push_back(0);
    for(int i=head[root];i;i=e[i].next) {
        int son=e[i].v;
        if(vis[son]) continue;
        disi=1;
        get_dis(son,root,e[i].w);
        for(int j=1;j<=disi;j++)
            for(int k=0;k<ok.size();k++)
                if(dis[j]+ok[k]<=1e7) ans[dis[j]+ok[k]]=true;
        for(int j=2;j<=disi;j++)
            ok.push_back(dis[j]);
    }
    ok.clear();
    for(int i=head[root];i;i=e[i].next) {
        int son=e[i].v;
        if(son==father||vis[son]) continue;
        solve(son,root,siz[son]);
    }
}

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);
    }
    solve(1,0,n);
    ans[0]=true;
    while(m--) {
        int x;
        scanf("%d",&x);
        if(ans[x]) printf("AYE\n");
        else printf("NAY\n");
    }
    return 0;
}