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

概念

关于下面介绍的性质的证明，主要参考博客
计算以无根树每个点为根节点时的最大子树大小，这个值最小的点称为无根树的重心。

性质

用$siz{e}_u(v)$表示以u为根节点时包含v的子树的大小。

找重心

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);
}

例题

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

#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;
}