树的重心

发布于 2020-09-28  0 次阅读


概念:

树的重心

性质:

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

重心的求解方法:

任选一个结点作为根节点用dfs求解
用siz记录子节点个数,son记录删除该点后最大连通分量的子树的节点个数
当s o n [ u ] ∗ 2 < = n son[u]*2 <= nson[u]∗2<=n时记录一下,最多两个结点

Code:

void dfs(int u, int fa){
    siz[u]=1, son[u]=0;
    for(auto v:g[u]){
        if(v!=fa){
            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]*2 <= n)   r2=r1, r1=u;
    return ;
}

平平无奇的大学在读本科生