点分治60pts求条

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 9,M = 109,K = 1e7 + 9;
int n,m;
struct edge{
    int to,cost,nex;
} e[N << 1];
int head[N],ecnt;
void addedge(int u,int v,int w){
    ecnt++;
    e[ecnt] = (edge){v,w,head[u]};
    head[u] = ecnt;
}
int dp[N],siz[N],dis[N];
int rec[N],rec_top;//记录出现过的距离
int tmp[K],tmp_top;
bool vis[N];
int query[M];
bool exist[K],ans[M];
int tot,Center;
void get_center(int u,int fa){//寻找重心 
    dp[u] = 0;siz[u] = 1;
    for(int i = head[u];i;i = e[i].nex){
        int v = e[i].to,w = e[i].cost;
        if(vis[v] || v == fa)
            continue;
        get_center(v,u);
        siz[u] += siz[v];
        dp[u] = max(dp[u],siz[v]);
    }
    if(max(dp[u],tot - siz[u]) < dp[Center])
        Center = u;
}
void get_dis(int u,int fa){//获得子树所有节点及到根的距离 
    rec[++rec_top] = dis[u];
    for(int i = head[u];i;i = e[i].nex){
        int v = e[i].to,w = e[i].cost;
        if(vis[v] || v == fa)
            continue;
        dis[v] = dis[u] + w;
        get_dis(v,u);
    }
}
void merge(int u){//合并答案 
    tmp_top = 0;
    for(int i = head[u];i;i = e[i].nex){
        int v = e[i].to,w = e[i].cost;
        if(vis[v])
            continue;
        rec_top = 0;dis[v] = w;
        get_dis(v,u);
        for(int j = 1;j <= rec_top;j++)
            for(int k = 1;k <= m;k++)
                if(query[k] >= rec[j])
                    ans[k] |= exist[query[k] - rec[j]];
        for(int j = 1;j <= rec_top;j++){
            tmp[++tmp_top] = rec[j];
            exist[rec[j]] = true;
        }
    }
    for(int i = 1;i <= tmp_top;i++)
        exist[tmp[i]] = false;
}
void solve(int u){//点分治主体 
    vis[u] = true;
    merge(u);
    for(int i = head[u];i;i = e[i].nex){
        int v = e[i].to,w = e[i].cost;
        if(vis[v])
            continue;
        dp[0] = n;Center = 0;tot = siz[v];
        get_center(v,u);
        solve(Center);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 1;i < n;i++){
        int u,v,w;
        cin >> u >> v >> w;
        addedge(u,v,w);
        addedge(v,u,w);
    }
    for(int i = 1;i <= m;i++)
        cin >> query[i];
    dp[0] = tot = n;
    get_center(1,0);
    exist[0] = true;
    solve(Center);
    for(int i = 1;i <= m;i++)
        cout << (ans[i] ? "AYE" : "NAY") << '\n';
    return 0;
}