树--树的重心

树的重心

树的重心也叫树的质心。找到一个点,其所有的子树中最大的子树节点数最少，那么这个点就是这棵树的重心，删去重心后，生成的多棵树尽可能平衡。

一棵有根树至多有两个重心

思路

把无根树变成有根树，任意选定一个根，进行dfs

统计每一个点，以它子节点为根的所有树里面节点数的最大值，如果最大值小于已知的最大值，更新重心

code

int head[maxn],to[maxn],Next[maxn],cnt = 1;		//链式前向星

void add(int u,int v)
{
    to[cnt] = v;Next[cnt] = head[u];head[u] = cnt;cnt++;
}

int d[maxn];		//记录每个节点的子树大小

int minnode,minbalance = inf;     //重心,最大节点个数

void dfs(int u,int pre)
{
    d[u] = 1;
    int maxsub = 0;       //节点u的最大子树节点个数
    for(int i = head[u]; i ; i = Next[i])
    {   
        int v = to[i];
        if(v == pre) continue;
        dfs(v,u);
        d[u] += d[v];
        maxsub = max(maxsub,d[v]);
    }
    maxsub = max(maxsub,n-d[u]);        //pre那边的子树节点个数
    if(maxsub < minbalance)             //更新答案
    {
        minnode = u;
        minbalance = maxsub;
    }
}

//dfs(1,0)

例题

牛客-tree