树的重心专题

清疚 2023-08-17 16:26 78阅读 0赞

解题思路：选择一个节点作为根，设dp\[i\]表示以i为根的树的总节点个数，dp\[i\]=满足j为其子节点的的d\[j\]之和再加1（根节点）。只需在dfs过程中找到最大的子树节点，并与其上方的节点数做比较，就可以找出树的重心了。

题目大意：对于一棵无根树，找到一个点使得树以该点为根的有根树，最大子树（选择该节点后其子树的最大节点）的节点数最小。

[https://blog.csdn.net/qq\_41289920/article/details/83933631][https_blog.csdn.net_qq_41289920_article_details_83933631]

[https://blog.csdn.net/llzhh/article/details/78146548][https_blog.csdn.net_llzhh_article_details_78146548]

[https://blog.csdn.net/imzxww/article/details/81776219][https_blog.csdn.net_imzxww_article_details_81776219]

模板：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    #include<vector>
    #include<queue>
    #include<utility>
    #include<stack>
    #include<algorithm>
    #include<cstring>
    #include<string>
    #include<cmath>
    #include<set>
    #include<map>
    using namespace std;
    const int maxn = 5e4 + 5;
    int head[maxn], to[maxn << 1], nx[maxn << 1], tot;
    bool vst[maxn];
    int Min = 0x3f3f3f3f, key;
    int cnt[maxn], n; 
    vector <int> vec; 
     
    void add_edge(int u, int v) {
        to[tot] = v, nx[tot] = head[u], head[u] = tot++;
        swap(u, v);
        to[tot] = v, nx[tot] = head[u], head[u] = tot++;
    }
     
    int dfs(int u, int par) {
        cnt[u] = 1;
        int Max = 0;
        for(int i = head[u]; ~i; i = nx[i]) {
            int v = to[i];
            if(v != par) {
                cnt[u] += dfs(v, u);
                Max = max(Max, cnt[v]);
            }
        }
        if(Max < n - cnt[u])
            Max = n - cnt[u];
        if(Max < Min) {
            vec.clear();
            Min = Max;
            vec.push_back(u);
        } else if(Max == Min) {
            vec.push_back(u);
        }
        return cnt[u];
    }
     
    int main() {
        memset(head, -1, sizeof(head));
        tot = 0;
        Min = 0x3f3f3f3f;
        scanf("%d", &n);
        for(int i = 1, u, v; i < n; i++) {
            scanf("%d%d", &u, &v);
            add_edge(u, v);
        }
        dfs(1, 1);
        sort(vec.begin(), vec.end());
        for(int i = 0; i < vec.size(); i++)
            printf("%d%c", vec[i], i + 1 == vec.size() ? '\n' : ' ');
    return 0;
    }

#include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<algorithm>
    #include<vector>
    using namespace std;
    #define inf 1<<30
     
    int n,dp[101],node,minans;    
    vector<int> edge[101];
     
    int dfs(int m,int fa)
    {
        int maxnode=0;
        for(int i=0;i<edge[m].size();i++)
        {
            int tmp=edge[m][i];
            if(tmp!=fa) 
            {
                dp[m]+=dfs(tmp,m);
                maxnode=max(maxnode,dp[tmp]);   //得到最大子树节点数 
            }
        }
        maxnode=max(maxnode,n-dp[m]);   //再与上方的节点数做比较 
        if(maxnode<minans)
        {
            minans=maxnode;
            node=m;
        }
        return dp[m];
    }
     
    int main()
    {
        while(cin>>n)
        {
            for(int i=1;i<=n;i++) edge[i].clear();
            int a,b;
            for(int i=1;i<=n-1;i++)
            {
                cin>>a>>b;
                edge[a].push_back(b);
                edge[b].push_back(a);
            }
            for(int i=1;i<=n;i++)    //初始化都是1，即根节点本身 
            {
                dp[i]=1;
            }
            minans=inf;
            dfs(1,-1);
            cout<<minans<<" "<<node<<endl;
        }
        return 0;
    }

树的带权重心：----解释版：[https://blog.csdn.net/qq\_35781950/article/details/76854246][https_blog.csdn.net_qq_35781950_article_details_76854246]

#include<bits/stdc++.h>//树的重心版本
    using namespace std;
    const int maxn=4e5+20;
    struct Node{
           int to;
           int next;
    }node[maxn];
    int len;
    int head[maxn];
    void add(int a,int b){
         node[len].to=b;
         node[len].next=head[a];
         head[a]=len++;
    }
    int m;
    bool vis[maxn];
    int c_tre[maxn];
    int num[maxn];
    bool visit[maxn];//对应权重点
    int k;
    long long all=0;
    int bkbk;
    void Init(){
    len=0;
    memset(head,-1,sizeof(head));
    memset(vis,false,sizeof(vis));
    memset(c_tre,0,sizeof(c_tre));
    memset(visit,false,sizeof(visit));
    memset(num,0,sizeof(num));
    all=0;
    bkbk=0;
    }
    void dfs1(int x,int pre){
        if(visit[x]) {num[x]=1;}
        for(int i=head[x];i!=-1;i=node[i].next){
            int to=node[i].to;
            if(to==pre)continue;
            dfs1(to,x);
            num[x]+=num[to];
        }
        return ;//返回的这个num 带自身。
    }
    void dfs(int u,int fa)//求树的带权重心模板。
    {
        int mx=k*2-num[u];
        for(int i=head[u]; i!=-1; i=node[i].next)
        {
            int v=node[i].to;
            if(v==fa) continue;
            mx=max(mx,num[v]);
        }
        if(mx<=k){
            bkbk=u;
            return ;
        }
        for(int i=head[u]; i!=-1; i=node[i].next)
        {
            int v=node[i].to;
            if(v==fa) continue ;
            dfs(v,u);
            if(bkbk) return ;
        }
    }
    void  dfs3(int c,int len){
        //这个搜索的过程是 累加求每个点距离重心的距离
         vis[c]=true;
         if(visit[c]) all+=len;
         for(int i=head[c];i!=-1;i=node[i].next){
              int to=node[i].to;
              if(vis[to]) continue;
              dfs3(to,len+1);
         }
    }
    int main()
    {   int t;
        int a,b;
        scanf("%d%d",&m,&k);
              Init();
              for(int i=0;i<2*k;i++){
                 scanf("%d",&a);
                 visit[a]=true;
              }
              //k*=2;
              for(int i=0;i<m-1;i++){
                  scanf("%d%d",&a,&b);
                  add(b,a);
                  add(a,b);
              }
              dfs1(1,-1);//记录一下权重.
              dfs(1,-1);//计算一下带权重心。
              all=0;
              memset(vis,false,sizeof(vis));
              dfs3(bkbk,0);//计算一下各个点距离 重心的权重和。
              cout<<all<<endl;
        return 0;
    }

[https://blog.csdn.net/q1093383371/article/details/52985375][https_blog.csdn.net_q1093383371_article_details_52985375]

#include<cstdio>
    #include<vector>
    #include<iostream>
    #include<queue>
    #include<cstring>
    #define maxn 200005
    using namespace std;
    //找树的重心 
    int n,popu[maxn],tot=0;
    vector<int>g[maxn];
    
    void init()
    {
        scanf("%d",&n);//表示乡镇数量 
        int x,y;
        for(int i=1;i<n;i++)//n-1表示形成树的边 
        {
            scanf("%d%d",&x,&y);
            g[x].push_back(y);
            g[y].push_back(x);
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&popu[i]);//权值 
            tot+=popu[i];//权值总和 
        }
    }
    
    bool vis[maxn];
    int fa[maxn],sum[maxn],dist[maxn],maxsum[maxn];
    long long cost[maxn];
    
    void DFS(int i)
    {
        vis[i]=true;
        sum[i]=popu[i];
        cost[i]=0;
        for(int k=0;k<g[i].size();k++)
        {
            int j=g[i][k];
            if(vis[j]) continue;
            DFS(j);
            sum[i]+=sum[j];
            maxsum[i]=max(maxsum[i],sum[j]);
            cost[i]+=cost[j]+sum[j];
        }
        maxsum[i]=max(maxsum[i],tot-sum[i]);
    }
    
    void solve()
    {
        init();
        DFS(1);
        int sum_min=tot,x;
        for(int i=1;i<=n;i++)
        {
            if(maxsum[i]<sum_min)
            {
                sum_min=maxsum[i];
                x=i;
            }
        }
        for(int i=1;i<=n;i++)
        {
            if(maxsum[i]==sum_min)
            {
                printf("%d ",i);
            }
        }
        printf("\n");
        memset(vis,0,sizeof(vis));
        DFS(x);
        cout<<cost[x]<<endl;
    }
    
    int main()
    {
        //freopen("in.txt","r",stdin);
        solve();
        return 0;
    }

转载于:https://www.cnblogs.com/Aiahtwo/p/11518735.html

[https_blog.csdn.net_qq_41289920_article_details_83933631]: https://blog.csdn.net/qq_41289920/article/details/83933631
[https_blog.csdn.net_llzhh_article_details_78146548]: https://blog.csdn.net/llzhh/article/details/78146548
[https_blog.csdn.net_imzxww_article_details_81776219]: https://blog.csdn.net/imzxww/article/details/81776219
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230810/5efec8a76e024ad3a94ceb38b56b992c.png
[https_blog.csdn.net_qq_35781950_article_details_76854246]: https://blog.csdn.net/qq_35781950/article/details/76854246
[https_blog.csdn.net_q1093383371_article_details_52985375]: https://blog.csdn.net/q1093383371/article/details/52985375