题解 P3806

点分治模板题。

点分治适合处理大规模的树上路径信息问题

暴力做法：dfs 每个点 \(u\)，算出其子树内每个点到 \(u\) 的距离，统计经过 \(u\) 的所有路径，复杂度 \(O(n^2)\)。

容易发现，复杂度和子树大小有关。

对于当前子树，我们可以求出其重心，计算经过重心的所有路径，删掉重心，递归每个联通块。

复杂度分析：如果我们将分治重心按 BFS 那样分层，那么每一层所有分治重心所代表的联通块的大小之和为 \(n\)。而因为重心最大的子树小于总点数的一半，所以最多有 \(\log n\) 层。总复杂度 \(O(n\log n)\)。

code:

#include <bits/stdc++.h>
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
const int N = 1e4 + 5, N2 = 1e7 + 5;
int n, m, sum, rt = 0, tot = 0, cnt = 0, f[N], siz[N], q[N], d[N], vis[N], pd[N2], ok[N2], tmp[N], cl[N];
struct edge{
    int v, w;
    edge(int v = 0, int w = 0):v(v), w(w){}
};
vector<edge> adj[N];
void dfszhong(int u, int lst) {
    siz[u] = 1;
    int maxn = 0;
    for (int i = 0; i < adj[u].size(); ++i) {
        int v = adj[u][i].v;
        if (v != lst && !vis[v]) {
            dfszhong(v, u);
            siz[u] += siz[v];
            if (siz[v] > maxn) maxn = siz[v];
        }
    }
    if (sum - siz[u] > maxn) maxn = sum - siz[u];
    f[u] = maxn;
    if (maxn < f[rt]) rt = u;
}
void getd(int u, int lst) {
    tmp[++tot] = d[u];
    for (int i = 0; i < adj[u].size(); ++i) {
        int v = adj[u][i].v, w = adj[u][i].w;
        if (v != lst && !vis[v]) {
            d[v] = d[u] + w;
            getd(v, u);
        }
    }
}
void getans(int u) {
    cnt = 0;
    for (int i = 0; i < adj[u].size(); ++i) {
        int v = adj[u][i].v, w = adj[u][i].w;
        if (vis[v]) continue;
        tot = 0; d[v] = w; getd(v, u);
        for (int j = 1; j <= tot; ++j) for (int k = 1; k <= m; ++k) if (q[k] >= tmp[j]) ok[q[k]] |= pd[q[k] - tmp[j]];
        for (int j = 1; j <= tot; ++j) if (tmp[j] <= 1e7) cl[++cnt] = tmp[j], pd[tmp[j]] = 1;
    }
    for (int i = 1; i <= cnt; ++i) pd[cl[i]] = 0;
}
void solve(int u) {
    vis[u] = pd[0] = 1; getans(u);
    for (int i = 0; i < adj[u].size(); ++i) {
        int v = adj[u][i].v;
        if (!vis[v]) {
            sum = siz[v]; rt = 0;
            dfszhong(v, u); solve(rt);
        }
    }
}
int main() {
    n = read(); m = read(); sum = n;
    for (int i = 1; i < n; ++i) {
        int u = read(), v = read(), w = read();
        adj[u].push_back(edge(v, w)); adj[v].push_back(edge(u, w));
    }
    for (int i = 1; i <= m; ++i) q[i] = read();
    f[0] = 1e9;
    dfszhong(1, 0); solve(rt);
    for (int i = 1; i <= m; ++i) {
        if (ok[q[i]]) printf("AYE\n");
        else printf("NAY\n");
    }
    return 0;
}