神树探索 - 力扣（LeetCode）

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
using pii = pair<int, int>;
const int N = 1e5 + 5;
int n, m, k, ans[N], fa[N], dep[N], sz[N], son[N], top[N], dfn[N], ed[N], tim, a[N], b[N], c[N], d[N], e[N], f[N], g[N];
vector<int> e1[N], e2[N];
void dfs1(int u, int f) {
    fa[u] = f, dep[u] = dep[f] + 1, sz[u] = 1;
    for (int v : e1[u])
        if (v != f) {
            dfs1(v, u);
            sz[u] += sz[v];
            if (sz[v] > sz[son[u]]) son[u] = v;
        }
}
void dfs2(int u, int tp) {
    top[u] = tp, dfn[u] = ++tim;
    if (son[u]) dfs2(son[u], tp);
    for (int v : e1[u])
        if (v != fa[u] && v != son[u])
            dfs2(v, v);
    ed[u] = tim;
}
int lca(int u, int v) {
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        u = fa[top[u]];
    }
    return dep[u] < dep[v] ? u : v;
}
int dis(int u, int v) { return dep[u] + dep[v] - 2 * dep[lca(u, v)]; }
void upd(int x, int v) {
    for (; x <= n; x += x & -x) ans[x] = min(ans[x], v);
}
int qry(int x) {
    int res = ans[x];
    for (x -= x & -x; x; x -= x & -x) res = min(res, ans[x]);
    return res;
}
void dfs(int u, int f) {
    for (int v : e2[u])
        if (v != f) {
            dfs(v, u);
            a[u] += a[v], b[u] += b[v], c[u] += c[v];
            d[u] += d[v], e[u] += e[v], f[u] += f[v];
        }
    if (u == 1) {
        a[u] = 1, b[u] = 0, c[u] = 0;
        d[u] = 0, e[u] = 0, f[u] = 0;
    } else if (dep[u] == 2) {
        a[u] = 0, b[u] = 1, c[u] = 0;
        d[u] = 0, e[u] = 0, f[u] = 0;
    } else {
        a[u] = 0, b[u] = 0, c[u] = 1;
        d[u] = 0, e[u] = 0, f[u] = 0;
        int x = qry(dfn[u]), y = qry(ed[u] + 1);
        if (x < 0x3f3f3f3f) e[u] = min(e[u], x + dis(u, b[x]));
        if (y < 0x3f3f3f3f) e[u] = min(e[u], y + dis(u, b[y]));
        if (x < 0x3f3f3f3f && y < 0x3f3f3f3f)
            f[u] = min(f[u], x + y + dis(u, b[x]) + dis(u, b[y]));
        if (a[u]) upd(dfn[u], d[u]), upd(ed[u] + 1, 0x3f3f3f3f);
        if (b[u]) upd(dfn[u], 0x3f3f3f3f), upd(ed[u] + 1, e[u]);
        if (c[u]) upd(dfn[u], f[u] - 2 * dep[u]), upd(ed[u] + 1, e[u] - dep[u]);
    }
}
int main() {
    scanf("%d", &n);
    rep(i, n - 1) {
        int u, v;
        scanf("%d%d", &u, &v);
        e1[u].push_back(v), e1[v].push_back(u);
    }
    dfs1(1, 0), dfs2(1, 1);
    scanf("%d", &m);
    rep(i, m) {
        int x;
        scanf("%d", &x);
        a[x] = 1;
    }
    memset(ans, 0x3f, sizeof ans);
    dfs(1, 0);
    rep(i, n) printf("%d\n", ans[dfn[i]]);
    return 0;
}