TLE on #7

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

const int N = 1e4 + 7;
bool flag = false;
int n, m, k, cnt, dl[N], delt[N], sz[N], mx[N], RT[N], lzx, lx, id = 0;
bool val[10000007], vis[N];
vector< pair<int,int> > g[N];

void getdis(int u, int fa, int sum){
    dl[++cnt] = sum;
    for(auto pi : g[u]){
        int v = pi.first, w = pi.second;
        if(v != fa && !vis[v]){
            getdis(v, u, sum + w);
        }
    }
    return;
}

void dfs(int u, int fa){
    sz[u] = 1; mx[u] = 0; dl[++cnt] = u;
    for(auto pi : g[u]){
        int v = pi.first, w = pi.second;
        if(v != fa && !vis[v]){
            dfs(v, u);
            mx[u] = max(mx[u], sz[v]);
            sz[u] += sz[v];
        }
    }
    return;
}

void solve(int x){
    int rt = RT[++id], tot = 0;
    vis[rt] = 1;
//  cout << x << ' ' << rt << '\n';
    for(pair<int, int> pi : g[rt]){
        int v = pi.first, w = pi.second;
        cnt = 0;
        if(vis[v]) continue;
        getdis(v, rt, w);
//      cout << "xxx:";
//      for(int i = 1; i <= cnt; i++)
//          cout << dl[i] << ' ';
//      cout << '\n';
        for(int i = 1; i <= cnt; i++)
            if(dl[i] == k || dl[i] < k && val[k - dl[i]]){
                flag = true; 
            }
        for(int i = 1; i <= cnt; i++){
            if(dl[i] <= 1e7 && !val[dl[i]]){
                delt[++tot] = dl[i];
                val[dl[i]] = 1; 
            }
        }
        cnt = 0;
    }
    for(int i = 1; i <= tot; i++)
        val[delt[i]] = 0;
    for(pair<int, int> pi : g[rt]){
        int v = pi.first, w = pi.second;
        if(!vis[v]) solve(v);
    }
    return;
}

void getrt(int u){
    cnt = 0;  
    dfs(u, 0);
    int rt = u, mi = 1e9;
    for(int i = 1; i <= cnt; i++){
        mx[dl[i]] = max(mx[dl[i]], sz[u] - sz[dl[i]]);
        if(mx[dl[i]] < mi){
            mi = mx[dl[i]];
            rt = dl[i];
        }
    }
    RT[++id] = rt;
    vis[rt] = 1;
    for(auto pi : g[rt]){
        int v = pi.first, w = pi.second;
        if(!vis[v]) getrt(v);
    }
    return;
}

signed 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;
        g[u].push_back(make_pair(v, w)); g[v].push_back(make_pair(u, w));
    }
    getrt(1);
    while(m--){
        cin >> k;   
        for(int i = 1; i <= n; i++)
            vis[i] = 0;
        flag = false; id = 0;
        solve(1);
        if(flag) cout << "AYE" << '\n';
        else cout << "NAY" << '\n';
    }
    return 0;
}

我是先建点分树再统一询问