树的重心

原理

见《进阶指南》第95页。

模板题

POJ-3107-Godfather

#include <iostream>
#include <cstring>
#define inf 0x3f3f3f3f
#define size SiZe
using namespace std;

const int N = 50010;
struct edge {
    int to, next;
};
edge e[2 * N];
int idx, head[N];
int n, dp[N], size[N];

void add_edge (int u, int v) {
    e[idx].to = v;
    e[idx].next = head[u];
    head[u] = idx ++;
}
void dfs (int cur, int fa) {
    size[cur] = 1;
    for (int i = head[cur]; i != -1; i = e[i].next) {
        int to = e[i].to;
        if (to != fa) {
            dfs(to, cur);
            size[cur] += size[to];
            dp[cur] = max(dp[cur], size[to]);
        }
    }
    dp[cur] = max(dp[cur], n - size[cur]); // 子树以外的部分
}

int main () {
    memset(head, -1, sizeof(head));
    scanf("%d", &n);
    for (int i = 1, u, v; i <= n - 1; ++ i) {
        scanf("%d%d", &u, &v);
        add_edge(u, v);
        add_edge(v, u);
    }

    dfs(1, -1);
    int min_size = inf;
    for (int i = 1; i <= n; ++ i) min_size = min(min_size, dp[i]);
    for (int i = 1; i <= n; ++ i)
        if (dp[i] == min_size)
            printf("%d ", i);
    return 0;
}