树的重心

红太狼 2023-07-10 08:22 2阅读 0赞

# 树的重心 #

> 说明：下面的定义等都是按照个人的理解所表述的，如有错误欢迎批评指出。

## 1.定义： ##

去掉该节点，最大的连通块（子树）的节点数目最少，则该节点点称作该树的重心。

## 2.性质： ##

*  去掉一个重心后，生成的每个连通块的节点数 <= 总节点数/2。
 *  重心可能不止一个，一棵树最多有两个重心，且相邻。
 *  树中所有点到重心的距离和最小。
 *  两棵树通过一条边相连，新树的重心一定在原来两棵树重心的连线上（不同树的两个重心所构成的路径）。
 *  一棵树添加或删除一个节点，树的重心最多移动一条边的位置。

## 3.实例： ##

如下图所示的一棵树，可以很容易的看出，这棵树的重心可以是2，也可以是3。去掉重心后，构成的最大连通块节点数为3。比如，去掉2，得到的连通块为：\{1\}，\{5\}，\{3,4,6\}。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RiX3lvdXRo_size_16_color_FFFFFF_t_70]

## 4.题目和解题模板： ##

入门题目：POJ 1655，POJ 3107。  
用树形dp来求解重心

#include <iostream>
    #include <cstring>
    #include <cstdio>
    using namespace std;
    const int N = 5e4+5;
    struct Edge
    {
        
        int from;
        int to;
        int next;
    } edge[N<<1];
    int head[N],id;
    /*
    dp[i]:存去掉i节点，所构成最大连通块的节点数目
    siz[i]:存储以i为根的子树节点的数目
    minx:去掉重心后，最大连通块的节点数目具体是多少，
    用于判断哪些点可以是重心
    */
    int dp[N],siz[N];
    int n,minx;
    void init2()
    {
        
        for(int i = 1; i <= n; i++)
        {
        
            dp[i] = 0;
            siz[i] = 1;
        }
        minx = 1 << 30;
    }
    void init()
    {
        
        memset(head,-1,sizeof(head));
        id = 0;
    }
    inline void add_edge(int from,int to)
    {
        
        edge[id].from = from;
        edge[id].to = to;
        edge[id].next = head[from];
        head[from] = id++;
    }
    
    void dfs(int u,int fa)
    {
        
        for(int i = head[u]; ~i; i = edge[i].next)
        {
        
            int to = edge[i].to;
            if(to != fa)
            {
        
                dfs(to,u);
                siz[u] += siz[to];
                dp[u] = max(dp[u],siz[to]);
            }
        }
        dp[u] = max(dp[u],n-siz[u]);
        minx = min(minx,dp[u]);
        return;
    }
    int main()
    {
        
        scanf("%d",&n);
        init();
        for(int i = 1; i < n; i++)
        {
        
            int x,y;
            scanf("%d%d",&x,&y);
            add_edge(x,y);
            add_edge(y,x);
        }
        init2();
        dfs(1,0);
        bool flag = true;
        for(int i = 1; i <= n; i++)
        {
        
            if(dp[i] == minx)
            {
        
                if(flag)
                {
        
                    printf("%d",i);
                    flag = false;
                    continue;
                }
               printf(" %d",i);
            }
        }
        puts("");
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RiX3lvdXRo_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200301123319267.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RiX3lvdXRo,size_16,color_FFFFFF,t_70