树的重心

时间圣使·凡 · 2023-07-15 21:28:10 · 个人记录

树的重心

树的重心：找到一个点,其所有的子树中最大的子树节点数最少。 树的重心性质：

1、树中所有点到某个点的距离和中，到重心的距离和是最小的，如果有两个距离和，他们的距离和一样。

2、把两棵树通过一条边相连，新的树的重心在原来两棵树重心的连线上。

3、一棵树添加或者删除一个节点，树的重心最多只移动一条边的位置。

4、一棵树最多有两个重心，且相邻。

如何求树的重心？

一个节点的子树其实就是删除节点后的几个连通块，设f_{i}表示以 i 为根的子树的节点个数，显然有：f_{i}=∑f_{j}+1（j是i的子树）。

如何求节点2的最大联通分量的节点个数？ 我们删除节点2，可以得到3个联通分量：① ② ③。① ② 是节点2的子树，我们可以使用f[i]=∑f[j]+1递归求得；③是该节点上方的子树，该子树的节点数：n-f[i] 所以节点i的最大联通分量的节点数为：dp(i) = max(f[j],n-f[i]) （j是i的子树）

ll minl=INF,ans;
/*
sz数组表示以当前节点为根,向下的子树的节点数目
dp数组表示以当前节点为根,子树中最大节点数目是多少
*/
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;
    }
}

2、通过其他点到重心的距离和最小的性质去求。