树的重心:找到一个点,其所有的子树中最大的子树节点数最少.

树的重心性质
1.树中所有点到某个点的距离和中，到重心的距离和是最小的，如果有两个距离和，他们的距离和一样。
2.删除重心后所得的所有子树，节点数不超过原树的1/2，一棵树最多有两个重心；
3.把两棵树通过一条边相连，新的树的重心在原来两棵树重心的连线上。
4.一棵树添加或者删除一个节点，树的重心最多只移动一条边的位置。
5.一棵树最多有两个重心，且相邻。

树的重心dfs求

void dfs(int u,int fa)
{
    sz[u]=1;
    for(int i=head[u];i!=-1;i=edge[i].next)//链式前向星遍历
    {
        int e=edge[i].e;
        if(e!=fa)//无向图,不加这个会成环
        {
            dfs(e,u);
            sz[u]+=sz[e];//回溯加一下
            dp[u]=max(dp[u],sz[e]);//每次遍历完一颗子树都比较

        }
    }
    dp[u]=max(dp[u],n-sz[u]);//不要忽略向上的节点个数,比较完之后便是当前节点的最大子树节点
    if(minl>dp[u])
    {
        minl=dp[u];
        ans=u;
    }
}

洛谷P1395:

const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int ans = INF, po;
int h[N], ne[N], e[N], idx;
int w[N];
int n, sum;
bool st[N];
int dist[N];
int s[N];

void add (int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void dfs (int x) {
    s[x] = w[x];
    st[x] = true;
    int max_part = 0;
    for (int i = h[x]; i != -1; i = ne[i] ) {
        int y = e[i];
        if (st[y]) continue;
        dfs (y);
        s[x] += s[y];
        max_part = max (max_part, s[y]);
    }
    max_part = max (max_part,  sum - s[x]);
    if (max_part < ans) {
        ans = max_part;
        po = x;
    }
}
void dfs2 (int x) {
    st[x] = true;
    for (int i = h[x]; i != -1; i = ne[i]) {
        int y = e[i];
        if (st[y]) continue;
        dist[y] = dist[x] + 1;
        dfs2 (y);
    }
}
int main () {
    cin >> n;
    memset (h, -1, sizeof h);
    for (int i = 1; i <= n;i  ++) {
        int a, b, c;
        cin >> w[i] >> b >> c;
        if (b) {
            add (i, b), add (b, i);
        }
        if (c) {
            add (i, c); add (c, i);
        }
        sum += w[i];
    }
    int root = 1;
    dfs (root);
    memset (st, false, sizeof st);
    dfs2 (po);
    int ans = 0;
    for (int i = 1; i <= n; i ++) 
        ans += dist[i] * w[i];

    cout << ans << endl;
    return 0;
}

https://codeforces.com/contest/1406/problem/C
C. Link Cut Centroids
本题考查树的重心,要求删边加边保证重心唯一
思路：如果找到只有一个重心，那么直接删一个重心的直连边然后加回去就好了。如果找到两个重心，那么在其中一个重心上找到一个直连点不是另一个重心，删除连另外一个就好了.

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+100;
typedef long long LL;
vector<LL>g[maxn]; 
LL siz[maxn],son[maxn];
LL r1,r2,n; 
void dfs(LL u,LL fa)
{
    siz[u]=1;
    for(LL i=0;i<g[u].size();i++){
        LL v=g[u][i];
        if(v==fa) continue;
        dfs(v,u);
        siz[u]+=siz[v];
        son[u]=max(son[u],siz[v]);
    }
    son[u]=max(son[u],n-siz[u]);
    if((son[u]<<1)<=n) r2=r1,r1=u;
}
int main()
{
LL t;
  cin>>t;
  while(t--)
  {
    cin>>n;
    for(LL i=0;i<=n+10;i++)
     g[i].clear(),siz[i]=0,son[i]=0;
    for(LL i=1;i<n;i++)
    {
        LL x,y;cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    r1=r2=0;
    dfs(1,0);
    if(!r2){
        LL r3=g[r1][0];
        cout<<r1<<" "<<r3<<endl;
        cout<<r1<<" "<<r3<<endl;
    }
    else
    {
        LL r3=r1;
        for(LL i=0;i<g[r2].size();i++)
        {
            r3=g[r2][i];
            if(r3!=r1) break;
        }
        cout<<r3<<" "<<r2<<endl;
        cout<<r3<<" "<<r1<<endl;
    }
  }
return 0;
}