Author: lllyouo
Date: 20250311
tag: 树的重心
link: https://www.luogu.com.cn/problem/P1395

问题描述

link

分析

略

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N = 5e4 + 10;
vector<int> g[N];
int n, center, siz[N], maxs[N], dis[N], vis[N];

void dfs(int u, int fu) {
    siz[u] = 1; maxs[u] = 0;
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (v == fu) continue;
        dfs(v, u);
        siz[u] += siz[v];
        maxs[u] = max(maxs[u], siz[v]);
    }

    maxs[u] = max(maxs[u], n - siz[u]);
    if (maxs[u] < maxs[center] || (maxs[u] == maxs[center] && u < center))
        center = u;
}

void bfs() {
    memset(dis, 0x3f, sizeof dis);
    queue<int> q;
    q.push(center);
    dis[center] = 0;
    vis[center] = 1;

    while (q.size()) {
        int u = q.front();
        q.pop();
        for (int i = 0; i < g[u].size(); i++) {
            int v = g[u][i];
            if (vis[v]) continue;
            vis[v] = 1;
            dis[v] = dis[u] + 1;
            q.push(v);
        }
    }
}

int main() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int a, b; cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    center = 0, maxs[center] = 0x3f3f3f3f;
    dfs(1, 0);
    bfs();

    int ans = 0;
    for (int i = 1; i <= n; i++) ans += dis[i];
    cout << center << " " << ans << endl;
    
    return 0;
}