本人妹子 刚学点分治 #7#9TLE

感觉（只是感觉）自己好像把询问都放一起处理了 但还是被卡了（？）

是不是我的实现有问题……

#include <bits/stdc++.h>

using namespace std;

inline int read() {
    int tmp = 0, f = 1;
    char c = getchar();
    while(!isdigit(c)) {
        if(c == '-') f = -f;
        c = getchar();
    }
    while(isdigit(c)) tmp = (tmp << 1) + (tmp << 3) + (c ^ 48), c = getchar();
    return tmp * f;
}

inline void write(int x) {
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) write(x / 10);
    putchar((x % 10) ^ 48);
}

struct edge {
    int t, nxt, w, mk;
} e[20010];

int n, m, k[110], ans[110], head[10010], ep, vis[10010], sz[10010];

int buc[10000010];

inline void add_edge(int u, int v, int w) {
    ep++;
    e[ep].t = v;
    e[ep].nxt = head[u];
    e[ep].w = w;
    head[u] = ep;
}

int cnt2, q[10010];

void dfs(int x, int dep) {
    sz[x] = 1; vis[x] = dep; q[++cnt2] = x;
    for(int i = head[x]; i != -1; i = e[i].nxt) {
        if(e[i].mk || vis[e[i].t] == dep) continue ;
        dfs(e[i].t, dep);
        sz[x] += sz[e[i].t];
    }
}

int cent(int x, int dep) {
    cnt2 = 0; dfs(x, dep);
    int ans, res = 0x7fffffff;
    for(int i = 1; i <= cnt2; i++) {
        int mx = sz[x] - sz[q[i]];
        for(int j = head[q[i]]; j != -1; j = e[j].nxt) {
            if(e[j].mk || sz[e[j].t] > sz[q[i]]) continue ;
            mx = max(mx, sz[e[j].t]);
        }
        if(mx < res) ans = q[i], res = mx;
    }
    return ans;
}

int ti, vis2[10010], depth[10010];

void dfs2(int x, int fa) {
    vis2[x] = ti; q[++cnt2] = x;
    for(int i = head[x]; i != -1; i = e[i].nxt) {
        if(e[i].t == fa) continue ;
        depth[e[i].t] = depth[x] + e[i].w;
        dfs2(e[i].t, x);
    }
}

int rec[10010];

void divide(int x, int dep) {
    // cerr << x << " " << dep << endl;
    ti++; cnt2 = 0;
    for(int i = head[x]; i != -1; i = e[i].nxt) {
        if(e[i].mk) continue ;
        rec[e[i].t] = cnt2 + 1; depth[e[i].t] = e[i].w;
        dfs2(e[i].t, x);
        for(int j = 1; j <= m; j++) {
            if(ans[j]) continue ;
            for(int l = rec[e[i].t]; l <= cnt2; l++) {
                if(k[j] >= depth[q[l]] && buc[k[j] - depth[q[l]]]) {
                    ans[j] = 1;
                    break;
                }
            }
        }
        // cerr << e[i].t << ":" ;
        for(int j = rec[e[i].t]; j <= cnt2; j++) {
            if(depth[q[j]] <= (int)1e7) buc[depth[q[j]]]++;
            // cerr << q[j] << " " << depth[q[j]] + e[i].w << endl;
        }
        // cerr << endl;
    }
    // cerr << endl;
    for(int i = 1; i <= cnt2; i++) if(depth[q[i]] <= (int)1e7) buc[depth[q[i]]]--;
    for(int i = head[x]; i != -1; i = e[i].nxt) {
        if(e[i].mk) continue ;
        e[i].mk = e[i ^ 1].mk = 1;
        divide(cent(e[i].t, dep + 1), dep + 1);
    }
}

int main() {
    buc[0] = 1;
    memset(head, -1, sizeof(head)); ep = -1;
    n = read(), m = read();
    for(int i = 1; i < n; i++) {
        int u = read(), v = read(), w = read();
        add_edge(u, v, w);
        add_edge(v, u, w);
    }
    for(int i = 1; i <= m; i++) k[i] = read();
    divide(cent(1, 1), 1);
    for(int i = 1; i <= m; i++) puts(ans[i] ? "AYE" : "NAY");
    return 0;
}