定义

树的重心是指树上的某个节点，满足删除当前点之后，生成的树的大小的最大值最小。

性质

性质1

以树的重心为根，那么根节点的每棵子树的大小都小于等于\(\frac{n}{2}\)。

性质2

每棵子树的大小都小于等于\(\frac{n}{2}\)的点一定是这棵树的重心。即性质\(1\)的逆命题。

性质3

树中所有点到某个点的距离和中，到重心的距离和最小。

性质4

两棵树通过一条新边连接成一棵新树。新树的重心一定再原来两棵树的重心之间的简单路径上。

性质5

一棵树最多有两个重心

求树的重心

求树的重心有两种方法。

方法1

dfs一遍，处理出每个节点\(u\)的最大子树。对于父亲节点方向的子树。可以用\(n-siz[u]\)得到。

方法2

“调整法”。先假设当前点\(u\)为最优点。如果孩子\(v\)不满足\(n-siz[v] \geq siz[v]\)，那么树的重心一定再子树\(v\)中。否则u为树的重心。

代码(方法1)

//2019-01-06 19:14:32
///Author: wxyww
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 20000 + 100;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
struct node {
    int v,nxt;
}e[N * 2];
int head[N],ejs;
void add(int u,int v){ 
    e[++ejs].v = v;e[ejs].nxt = head[u];head[u] = ejs;
}
int siz[N],n,ans[N];
void dfs(int u,int father) {
    siz[u] = 1;
    for(int i = head[u];i;i = e[i].nxt) {
        int v = e[i].v;
        if(v == father) continue;
        dfs(v,u);
        siz[u] += siz[v];
        ans[u] = max(ans[u],siz[v]);
    }
    ans[u] = max(ans[u],n - siz[u]);
}
int main() {
    int T = read();
    while(T--) {
        ejs = 0;
        memset(ans,0,sizeof(ans));
        memset(siz,0,sizeof(siz));
        memset(head,0,sizeof(head));
        n = read();
        for(int i = 1;i < n;++i) {
            int u = read(),v = read();
            add(u,v);add(v,u);
        }
        dfs(1,0);
        int anss = 0;
        ans[0] = N;
        for(int i = 1;i <= n;++i) {
            if(ans[i] < ans[anss]) anss = i;
        }
        printf("%d %d\n",anss,ans[anss]);
    }

    return 0;
}