点分治

• 点分治处理树上的路径问题

• 例题：luogu P3806 【模板】点分治1

#include <cstdio>
#include <algorithm>

const int N = 1e4 + 5;

int read(int x = 0, int f = 1, char c = getchar()) {
    for (; c < '0' || c > '9'; c = getchar())
        if (c == '-') f = -1;
    for (; c >='0' && c <='9'; c = getchar())
        x = x * 10 + c - '0';
    return x * f;
}

struct Edge {
    int n, t, d;
}e[N*2];
int h[N], edc;

void Add(int x, int y, int z) {
    e[++edc] = (Edge) {h[x], y, z}; h[x] = edc;
}

bool v[N], b[N*1000], p[105];
int n, m, q[105], misz, szt, rt, sz[N], dis[N], tot, mq;

void Getrt(int x, int fa) {
    int mx = 0; sz[x] = 1;
    for (int i = h[x], y; i; i = e[i].n) {
        if (v[y=e[i].t] || y == fa) continue;
        Getrt(y, x); sz[x] += sz[y];
        mx = std::max(mx, sz[y]);
    }
    mx = std::max(mx, szt - sz[x]);
    if (misz > mx) misz = mx, rt = x;
}

void Getsz(int x, int fa) {
    sz[x] = 1;
    for (int i = h[x], y; i; i = e[i].n)
        if (!v[y=e[i].t] && y != fa)
            Getsz(y, x), sz[x] += sz[y];
}

void Getd(int x, int fa, int d) {
    if (d > mq) return;
    dis[++tot] = d;
    for (int k = 1; k <= m; ++k)
        if (q[k] >= d) p[k] |= b[q[k]-d];
    for (int i = h[x], y; i; i = e[i].n)
        if (!v[y=e[i].t] && y != fa)
            Getd(y, x, d + e[i].d);
}

void Cal(int x) {
    b[0] = 1; tot = 0;
    for (int i = h[x], y; i; i = e[i].n) {
        if (v[y=e[i].t]) continue;
        int lt = tot + 1;
        Getd(y, 0, e[i].d);
        for (int j = lt; j <= tot; ++j) b[dis[j]] = 1;
    }
    for (int j = 1; j <= tot; ++j) b[dis[j]] = 0;
}

void Solve(int x) {
    v[x] = 1; Cal(x); Getsz(x, 0);
    for (int i = h[x], y; i; i = e[i].n) {
        if (v[y=e[i].t]) continue;
        misz = n; szt = sz[y];
        Getrt(y, 0); Solve(rt);
    }
}

int main() {
    n = read(); m = read();
    for (int i = 1; i < n; ++i) {
        int x = read(), y = read(), z = read();
        Add(x, y, z); Add(y, x, z);
    }
    for (int i = 1; i <= m; ++i) 
        q[i] = read(), mq = std::max(mq, q[i]);
    misz = szt = n; Getrt(1, 0); Solve(rt);
    for (int i = 1; i <= m; ++i)
        puts(p[i] || !q[i] ? "AYE" : "NAY");
    return 0;
}