树的重心

定义：

  1.找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重心后，生成的多棵树尽可能平衡。
  2.从树中去掉某点以及和该点相连的所有边后，整棵树变为许多"块"。去掉任意一个重心（相比于去掉其他点）可以使得生成的各个"块"的节点数的最大值最少。
  3.对于一棵树n个节点的无根树，找到一个点，使得把树变成以该点为根的有根树时，最大子树的结点数最小。

  实际上树的重心在树的点分治中有重要的作用, 可以避免N^2的极端复杂度（从退化链的一端出发），保证NlogN的复杂度, 利用树型dp可以很好地求树的重心。

<mark>树的重心性质</mark>：

1.树中所有的点到某个点的距离和中，到重心的距离和是最小的,如果有两个重心，那么他们的距离和一样；
2.把两棵树通过某一点（或边）相连得到一棵新的树，新树的重心必然在连接原来两棵树的重心的路径上；
3.一棵树删除一个或者添加一个节点，树的重心最多只移动一条边的距离;
4.以一棵树的重心为根的子树的节点个数，一定大于等于该树节点总数的一半;
5.从树中去掉某点以及和该点相连的所有边后，整棵树变为许多"块"，去掉任意一个重心后，生成的各个"块"的节点数的最大值一定小于等于原树的节点数除以2。

先看一道模板题：Balancing Act POJ - 1655

分析求解过程：

  在 $dfs$dfs 的过程中，用 $son\left[i\right]$son[i] 数组存以节点 $i$i 为根时，其子树的节点总数，可以在回溯的过程中计算。在计算平衡值时，要求求所有子树的节点数的最大值。对于节点 $i$i 的子节点，可以在回溯后进行比较。对于以父亲节点为根的子树，利用节点 $i$i 的子树节点数 + 父亲节点的子树的节点数 + 1 = n的关系，即可求出。比较便可得到平衡值。

模板：

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int N=2e4+5;
vector<int>pic[N];
int son[N];//存每个节点的子树的节点数
int balance,ans,n;
void dfs(int v,int p)
{
    son[v]=0;
    int res=0;
    for(int i=0;i<pic[v].size();i++)
    {
        int t=pic[v][i];
        if(t!=p)
        {
            dfs(t,v);
            son[v]+=son[t]+1;//找孩子所在子树的最大节点数
            res=max(res,son[t]+1);
        }
    }//看父亲节点所在子树的节点数
    res=max(res,n-son[v]-1);
    if(res<balance||res==balance&&v<ans)
    {
        ans=v;
        balance=res;
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int u,v;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            pic[i].clear();
        for(int i=1;i<n;i++)
        {
            scanf("%d%d",&u,&v);
            pic[u].push_back(v);
            pic[v].push_back(u);
        }
        balance=N<<1;
        ans=1;
        dfs(1,-1);
        printf("%d %d\n",ans,balance);
    }
    return 0;
}

Godfather POJ - 3107
求出所有的重心。

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int N=5e4+5;
int balance,n,cnt,cot;
struct node
{
    int to,next;
}edge[N<<1];
int head[N],ans[N],son[N];
void init()
{
    cot=1;
    memset(head,-1,sizeof(head));
}
void edgeadd(int from,int to)
{
    edge[cot].to=to;
    edge[cot].next=head[from];
    head[from]=cot++;
}
void dfs(int v,int p)
{
    son[v]=0;
    int res=0;
    for(int i=head[v];i!=-1;i=edge[i].next)
    {
        int t=edge[i].to;
        if(t!=p)
        {
            dfs(t,v);
            son[v]+=son[t]+1;
            res=max(res,son[t]+1);
        }
    }
    res=max(res,n-son[v]-1);
    if(res<balance)
    {
        cnt=0;
        ans[++cnt]=v;
        balance=res;
    }
    else if(res==balance)
        ans[++cnt]=v;
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        int u,v;
        init();
        for(int i=1;i<n;i++)
        {
            scanf("%d%d",&u,&v);
            edgeadd(u,v);
            edgeadd(v,u);
        }
        cnt=0;
        balance=N<<1;
        dfs(1,-1);
        sort(ans+1,ans+cnt+1);
        for(int i=1;i<=cnt;i++)
            printf("%d%c",ans[i],i==cnt?'\n':' ');
    }
    return 0;
}

codeforces 686D
求以每个点为根的子树的重心；
利用以上的性质2,3,4。

#include <bits/stdc++.h>
using namespace std;
const int N=3e5+5;
const int inf=0x3f3f3f3f;
vector<int>pic[N];
int size[N],ans[N],fa[N];
void dfs(int v)
{
    size[v]=1;
    ans[v]=v;
    int res=0,t=v;
    for(int i=0;i<pic[v].size();i++)
    {
        int u=pic[v][i];
        dfs(u);
        if(size[u]>res)
        {
            res=size[u];
            t=u;
        }
        size[v]+=size[u];
    }
    ans[v]=ans[t];
    while(size[v]>size[ans[v]]*2)//性质
        ans[v]=fa[ans[v]];
}
int main()
{
    int n,q,v;
    scanf("%d%d",&n,&q);
    fa[1]=1;
    for(int i=2;i<=n;i++)
    {
        scanf("%d",&v);
        pic[v].push_back(i);
        fa[i]=v;
    }
    dfs(1);
    for(int i=1;i<=q;i++)
    {
        scanf("%d",&v);
        printf("%d\n",ans[v]);
    }
    return 0;
}