点分治求查错

dis是到当前重心的距离

judge是是否有dis[u]这个值

#include <bits/stdc++.h>
#define debug cout<<"YES"<<endl;
using namespace std;
const int N = 1e4 + 5;

struct edge {
    int to,val;
}; 

vector <edge> V[N];

int n,m,root; 

int siz[N],ans[N],k[N],dis[N],Fa[N];

bool judge[10000005];
void add_edge(int u,int v,int w) {
    V[u].push_back((edge){v,w});
    V[v].push_back((edge){u,w});
}
void pre(int u,int fa) {
    siz[u] = 1;
    for(int i = 0;i < V[u].size();i ++) {
        int v = V[u][i].to;
        if(v == fa) continue;
        Fa[v] = fa;
        pre(v,u);
        siz[u] += siz[v];
    }
}
void find(int u,int fa,int gen) {
    int maxl = 0;
    for(int i = 0;i < V[u].size();i ++) {
        int v = V[u][i].to;
        if(v == fa) continue;
        find(v,u,gen);
        maxl = max(maxl,siz[v]);
    }
    maxl = max(maxl,siz[gen] - siz[u]);
    if(maxl <= siz[gen] / 2) root = u;
}
void add(int u,int fa) {
    judge[dis[u]] = 1; 
    for(int i = 0;i < V[u].size();i ++) {
        int v = V[u][i].to;
        if(v == fa) continue;
        add(v,u);
    }
}
void DFS(int u,int fa) {
    for(int i = 0;i < V[u].size();i ++) {
        int v = V[u][i].to;
        if(v == fa) continue;
        dis[v] = dis[u] + V[u][i].val;
        for(int j = 1;j <= m;j ++) {
            if(k[j] - dis[v] == 0) ans[j] = 1;
            else if(k[j] - dis[v] > 0 && judge[k[j] - dis[v]]) ans[j] = 1;
        }
        DFS(v,u);
        if(u == root) add(V[u][i].to,u);
    }
}
void clear(int u,int fa) {
    judge[dis[u]] = 0;
    dis[u] = 0;
    for(int i = 0;i < V[u].size();i ++) {
        int v = V[u][i].to;
        if(v == fa) continue;
        clear(v,u); 
    }
}
void dfs(int u,int fa) {
    find(u,fa,u);
    DFS(root,Fa[u]);
    clear(root,Fa[u]);
    for(int i = 0;i < V[u].size();i ++) {
        int v = V[u][i].to;
        if(v == fa) continue;
        dfs(v,u);
    }
}
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_edge(u,v,w);
    }
    for(int i = 1;i <= m;i ++) scanf("%d",&k[i]);
    pre(1,0);
    dfs(1,0);
    for(int i = 1;i <= m;i ++) {
        if(ans[i]) puts("AYE");
        else puts("NAY");
    }
    return 0;
}