【算法与数据结构】——树的重心

川长思鸟来 2022-09-13 11:27 200阅读 0赞

### 文章目录 ###

*  概念
 *  性质
 *  找重心
 *  例题

# 概念 #

关于下面介绍的性质的证明，主要参考博客[算法学习笔记(72): 树的重心][72_]  
计算以无根树每个点为根节点时的**最大子树**大小，这个值**最小**的点称为无根树的重心。

# 性质 #

用 s i z e u ( v ) size\_u(v) sizeu(v)表示以u为根节点时包含v的子树的大小。

1.  如果u和v相邻，那么 s i z e u ( v ) + s i z e v ( u ) = n size\_u(v)+size\_v(u)=n sizeu(v)\+sizev(u)=n。
2.  某个点是树的重心等价于它最大子树大小不大于整棵树大小的一半。
3.  树至多有两个重心。如果树有两个重心，那么它们相邻。此时树一定有偶数个节点，且可以被划分为两个大小相等的分支，每个分支各自包含一个重心。
4.  树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么到它们的距离和一样。反过来，距离和最小的点一定是重心。
5.  往树上增加或减少一个叶子，如果原节点数是奇数，那么重心可能增加一个，原重心仍是重心；如果原节点数是偶数，重心可能减少一个，另一个重心仍是重心。
6.  把两棵树通过一条边相连得到一棵新的树，则新的重心在较大的一棵树一侧的连接点与较大的一棵树原重心之间的简单路径上。如果两棵树大小一样，则重心就是两个连接点。

# 找重心 #

int n, sz[MAXN], mss[MAXN]; // n：总节点数（请从外部传入），sz：树的大小，mss：最大子树大小
    vector<int> ctr; // 重心
    void dfs(int p, int fa = 0) // 找重心
    { 
        sz[p] = 1, mss[p] = 0;
        for (auto [to, w] : edges[p])
            if (to != fa)
            { 
                dfs(to, p);
                mss[p] = max(mss[p], sz[to]);
                sz[p] += sz[to];
            }
        mss[p] = max(mss[p], n - sz[p]);
        if (mss[p] <= n / 2) ctr.push_back(p);
    }

# 例题 #

题目大意[洛谷P3525 INS-Inspection][P3525 INS-Inspection]  
题目大意：（这个题目上自带的翻译有点问题，看我的这个题意比较好）  
一棵n个节点的树，行动中心S从1->N。从S出发前往任意一个未标记到的点(沿树上两点的唯一路径走)，标记该节点，然后返回S。相邻两次行动所经过的道路不允许有重复，最后一次标记后不需要返回，求路程总和的最小值。第i行输出行动中心为i时的答案，如果不可能则输出-1。  
思路：如果一个点不是重心，那么答案一定是-1。  
否则，就是深度和-最长链。  
注意，如果重心子树最大值为 n 2 \\frac\{n\}\{2\} 2n，那么最长链只能在这个子树里选。  
由于一颗树的重心最多有两个，暴力即可。

#include <bits/stdc++.h>
    using namespace std;
    const int maxn=1e6+10;
    int n,head[maxn],s[maxn],cnt,root1,root2,f[maxn]= { maxn*10};
    int d[maxn],dsum,maxx;
    bool vis[maxn];
    struct node { 
        int to,nt;
    } e[maxn*2];
    void Add(int from,int to) { 
        e[++cnt].to=to;
        e[cnt].nt=head[from];
        head[from]=cnt;
    }
    void getroot1(int u,int fa) { 
        s[u]=1;
        f[u]=0;
        for(int i=head[u]; i; i=e[i].nt) { 
            int v=e[i].to;
            if(v==fa)continue;
            getroot1(v,u);
            s[u]+=s[v];
            f[u]=max(f[u],s[v]);
        }
        f[u]=max(f[u],n-s[u]);
        if(f[u]<f[root1])
            root1=u;
    }
    void getdep(int u,int fa) { 
        vis[u]=1;
        for(int i=head[u]; i; i=e[i].nt) { 
            int v=e[i].to;
            if(!vis[v]&&v!=fa) { 
                d[v]=0;
                d[v]=d[u]+1;
                getdep(v,u);
            }
        }
        vis[u]=0;
    }
    void dfs(int u,int&ans,int fa) { 
        vis[u]=1;
        for(int i=head[u]; i; i=e[i].nt) { 
            int v=e[i].to;
            if(!vis[v]&&v!=fa) { 
                ans=max(ans,d[v]);
                dfs(v,ans,u);
            }
        }
        vis[u]=0;
    }
    int main() { 
        scanf("%d",&n);
        for(int i=1; i<=n-1; i++) { 
            int u,v;
            scanf("%d%d",&u,&v);
            Add(u,v);
            Add(v,u);
        }
        getroot1(1,0);//确定第一个重心
        for(int i=head[root1]; i; i=e[i].nt) { //确定第二个重心
            int v=e[i].to;
            if(f[v]==f[root1]) { 
                root2=v;
                break;
            }
        }
        for(int i=1; i<=n; i++)
            if(i==root1||i==root2) { //如果是重心
                dsum=0;
                maxx=0;
                memset(vis,0,sizeof(vis));
                memset(d,0,sizeof(d));
                getroot1(i,0);//构造以该重心为基础的s数组
                getdep(i,0);//构造以该重心为基础的d数组
                if(n%2==0&&f[i]==n/2) { //特判是否最大子树大小就为n/2
                    for(int j=head[i]; j; j=e[j].nt) { //在最大子树中找最大链
                        int v=e[j].to;
                        if(s[v]==n/2) { //最大深度
                            maxx=max(maxx,d[v]);
                            dfs(v,maxx,i);
                            break;
                        }
                    }
                } else
                    for(int j=1; j<=n; j++)maxx=max(maxx,d[j]);//最大深度
                for(int j=1; j<=n; j++)//深度和统计
                    dsum+=d[j];
                printf("%d\n",dsum*2-maxx);
            } else printf("-1\n");
        return 0;
    }

[72_]: https://zhuanlan.zhihu.com/p/357938161
[P3525 INS-Inspection]: https://www.luogu.com.cn/problem/P3525