【模板】树的重心 性质

性质

1. 以树的重心为根时，所有子树的大小都不超过整棵树大小的一半。

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

3. 把两棵树通过一条边相连得到一棵新的树，那么新的树的重心在连接原来两棵树的重心的路径上。

4. 在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离。

模板

Poj 1655 balancing act
求重心以及去除重心后的最大子树大小

/*
 * @Autor: valk
 * @Date: 2020-07-17 16:50:40
 * @LastEditTime: 2020-08-14 10:41:23
 * @Description: 如果邪恶 是 华丽残酷的乐章 它的终场 我会亲手写上 晨曦的光 风干最后一行忧伤 黑色的墨 染上安详
 */

#include <algorithm>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stack>
#include <stdio.h>
#include <string.h>
#include <string>
#include <vector>
#define emplace_back push_back
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int mod = 1e9 + 7;
const int seed = 12289;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const int N = 2e5 + 10;

int n;
int sz[N], mxsz[N];
vector<int> vec[N];

void dfs(int u, int fa)
{
    sz[u] = 1, mxsz[u] = 0;
    for (int i = 0; i < vec[u].size(); i++) {
        int v = vec[u][i];
        if (v == fa)
            continue;
        dfs(v, u);
        sz[u] += sz[v];
        mxsz[u] = max(mxsz[u], sz[v]);
    }
    mxsz[u] = max(n - sz[u], mxsz[u]);
}

int main()
{
    int _;
    scanf("%d", &_);
    while (_--) {
        scanf("%d", &n);
        for (int i = 1; i < n; i++) {
            int u, v;
            scanf("%d%d", &u, &v);
            vec[u].pb(v), vec[v].pb(u);
        }
        dfs(1, 1);
        int minn = inf;
        for (int i = 1; i <= n; i++) {
            minn = min(minn, mxsz[i]);
            vec[i].clear();
        }
        int ans;
        for (int i = n; i ; i--) {
            if (mxsz[i] == minn) {
                ans = i;
            }
        }
        printf("%d %d
", ans, minn);
    }
    return 0;
}