神树探索 - 力扣（LeetCode）

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, ans[N], f[N][2], g[N][2], h[N][2], sz[N];
vector<int> G[N];
void dfs1(int u, int fa) {
    sz[u] = 1;
    for (auto v : G[u]) {
        if (v == fa) continue;
        dfs1(v, u);
        sz[u] += sz[v];
        f[u][0] += f[v][1] + sz[v];
    }
    for (auto v : G[u]) {
        if (v == fa) continue;
        f[u][1] = min(f[u][1], f[u][0] - f[v][1] - sz[v] + f[v][0] + n - sz[v]);
    }
}
void dfs2(int u, int fa) {
    for (auto v : G[u]) {
        if (v == fa) continue;
        g[v][0] = g[u][1] + n - sz[v] - sz[v];
        g[v][1] = g[u][0] - f[v][1] - sz[v] + f[v][0] + n - sz[v];
        dfs2(v, u);
    }
}
void dfs3(int u, int fa) {
    for (auto v : G[u]) {
        if (v == fa) continue;
        h[v][0] = h[u][1] + sz[v] + sz[v];
        h[v][1] = h[u][0] - f[v][1] - sz[v] + f[v][0] + sz[v] + sz[v];
        dfs3(v, u);
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 1, u, v; i < n; i++) {
        scanf("%d%d", &u, &v);
        G[u].push_back(v), G[v].push_back(u);
    }
    memset(f, 0x3f, sizeof(f));
    f[1][0] = 0;
    dfs1(1, 0);
    g[1][0] = 0, g[1][1] = f[1][1];
    dfs2(1, 0);
    h[1][0] = 0, h[1][1] = f[1][0];
    dfs3(1, 0);
    for (int i = 0; i < n; i++) {
        ans[i] = min(g[1][0] + h[1][i], g[1][1] + h[1][i]);
    }
    for (int i = 0; i < n; i++) {
        printf("%d\n", ans[i]);
    }
    return 0;
}