树的重心：

https://zhuanlan.zhihu.com/p/357938161

性质1

某个点是树的重心等价于它最大子树大小不大于整棵树大小的一半。

性质2

树至多有两个重心。如果树有两个重心，那么它们相邻。此时树一定有偶数个节点，且可以被划分为两个大小相等的分支，每个分支各自包含一个重心。

性质3

树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么到它们的距离和一样。反过来，距离和最小的点一定是重心。

性质4

往树上增加或减少一个叶子，如果原节点数是奇数，那么重心可能增加一个，原重心仍是重心；如果原节点数是偶数，重心可能减少一个，另一个重心仍是重心

性质5

把两棵树通过一条边相连得到一棵新的树，则新的重心在较大的一棵树一侧的连接点与原重心之间的简单路径上。如果两棵树大小一样，则重心就是两个连接点

找重心

利用性质1，一趟dfs即可。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int e[N], ne[N], h[N], idx = 0, res = 0;
int n, a, b;
bool st[N];


void add(int a, int b)  // 添加一条边a->b
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
int dfs(int u){
    st[u] = true;
    int sum = 1, part = 0, part_max = 0;
    for (int i = h[u]; i != -1; i = ne[i] ){
        int j = e[i];
        if(!st[j]) part = dfs(j), part_max = max(part, part_max), sum += part;
    }
    part = n - sum;
    res = max(part, part_max);
    return sum;
}

int main()
{
    memset(h, -1, sizeof h);
    cin >> n;
    for (int i = 1; i < n; i ++ ){
        scanf("%d%d", &a, &b);
        add(a, b);
        add(b, a);
    }
    dfs(1);
    cout << res <<endl;
    return 0;
}