树的重心 图论

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 5e4 + 10;
vector<int>e[N];
int cnt[N], sum, n, id = 1, ans;
void dfs1(int u, int fa ,int d)
{
    sum += d;
    cnt[u] = 1;
    for (auto it : e[u])
    {
        if (it != fa)
        {
            dfs1(it, u, d + 1);
            cnt[u] += cnt[it];
        }
    }
}
void dfs2(int u, int fa, int sum)
{
    if (sum < ans || (sum == ans && id > u))
    {
        id = u;
        ans = sum;
    }
    for (int it : e[u])
    {
        if (it != fa)
        {
            dfs2(it, u, sum - cnt[it] + n - cnt[it]);
        }
    }
}
int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n - 1; i++)
    {
        int x, y;
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs1(1, 0, 0);
    ans = sum;
    dfs2(1, 0, sum);
    cout << id << ' ' << ans;
    return 0;
}