CSP-S2019学习笔记：树的重心

àì夳堔傛蜴生んèń 2023-07-11 06:24 21阅读 0赞

2019年CSP提高组考了3题跟树有关的题：《括号树》、《树上的数》和《树的重心》。

《树的重心》这一题，题意比较好理解，通读两三遍题目后，再看一下样例1的解释，就能理解题意。

我在学习的过程中发到有人用到了向下倍增和两次深度优先搜索，在深度优先搜索的过程中还做了换根操作。这种解法真是非常精妙，让我受益匪浅。

因为之前做2018年NOIP提高组的《保卫王国》的时候，学过倍增，这次恰巧碰到这题再复习一下倍增，这样对倍增有了更加深刻的认识。倒是在寻找重心及换根的过程中，花了不少时间来学习。

这题的题目难度是省选，我用了三天的时间才学明白，不过比起另一道省选难度的题《划分》所用的五天时间，还是幸运了不少。

最后附上AC代码：

#include<bits/stdc++.h>
    using namespace std;
    
    const int maxN = 300005;
    //const int depth = 2;
    const int depth = 17;
    
    int T, n;
    int cnt;            
    int head[maxN];    
    int nodeCnt[maxN];  
    int nodeCnt2[maxN];
    int father[maxN];  
    int father2[maxN];  
    int heavySon[maxN]; 
    int heavySon2[maxN];
    int newHeavySon[maxN];
    int down[maxN][18];
    long long ans;
    
    struct edge
    {
        int to;
        int next;
    }e[maxN*2];
    
    void add(int x, int y)
    {
        ++cnt;
        e[cnt].to = y;
        e[cnt].next = head[x];
        head[x] = cnt;
    }
    
    void dfs(int x, int fa)
    {
        nodeCnt[x] = 1; 
        father[x] = fa;
    
        for(int i = head[x]; i; i = e[i].next)
        {
            int y = e[i].to;
            if(y == fa)
            {
                continue;
            }
    
            dfs(y, x);
    
            nodeCnt[x] += nodeCnt[y];
    
            if(nodeCnt[y] > nodeCnt[heavySon[x]])
            {
                heavySon2[x] = heavySon[x];  
                heavySon[x] = y;          
            }
            else if(nodeCnt[y] > nodeCnt[heavySon2[x]])
            {
                heavySon2[x] = y;
            }
        }
    
        down[x][0] = heavySon[x];
        for(int i = 1; i <= depth; i++)
        {
            down[x][i] = down[down[x][i-1]][i-1];
        }
    }
    
    //求质心之和
    int getCentSum(int x, int _nodeCnt)
    {
        int heavyChainSize = nodeCnt2[newHeavySon[x]]; 
        int otherSize = _nodeCnt - nodeCnt2[x]; 
        int maxSize = max(heavyChainSize, otherSize);
        bool flag = (maxSize <= _nodeCnt / 2);
        return x * flag;
    }
    
    void dfs2(int x, int fa)
    {
        for(int i = head[x]; i; i = e[i].next) 
        {
            int y = e[i].to;
            if(y == fa)
            {
                continue;
            }
    
            nodeCnt2[x] = nodeCnt[1] - nodeCnt[y];//被分割后含x那一棵子树里有多少个节点
            father2[y] = 0; //为换根作准备
            father2[x] = 0;
    
            if(heavySon[x] == y)    //y是x的重子节点
            {
                //y是x的重子节点，因为x和y之间的边已经被删除了，所以x的第二重子节点变成了重子节点
                newHeavySon[x] = heavySon2[x];
            }
            else
            {
                //重子节点和父节点x仍然在同一棵树里，则重子节点仍为重子节点
                newHeavySon[x] = heavySon[x];
            }
    
    
            if(nodeCnt2[fa] > nodeCnt2[newHeavySon[x]])
            {//换根后，旧的父节点（已变成子节点）成了重子节点
                newHeavySon[x] = fa;
            }
    
            //删除边后重新预处理x节点的重链
            down[x][0] = newHeavySon[x];
            for(int j = 1; j <= depth; j++)
            {
                down[x][j] = down[down[x][j-1]][j-1];
            }
    
            int cent = x; //重心
            for(int j = depth; j >= 0; j--)
            {
                if(nodeCnt2[x] - nodeCnt2[down[cent][j]] <= nodeCnt2[x] / 2)
                {
                    cent = down[cent][j]; //找分裂出的第一棵树的重心
                }
            }
    
            //若节点x不是重心,重心要么在x的重儿子子树里,要么在x的父节点上
            ans += getCentSum(newHeavySon[cent], nodeCnt2[x]) + getCentSum(cent, nodeCnt2[x]) + getCentSum(father2[cent], nodeCnt2[x]);
    
            cent = y;
            for(int j = depth; j >= 0; j--)
            {
                if(nodeCnt2[y] - nodeCnt2[down[cent][j]] <= nodeCnt2[y]/2)
                {
                    cent = down[cent][j]; //找分裂出的第二棵树的重心
                }
            }
    
            ans += getCentSum(newHeavySon[cent], nodeCnt2[y]) + getCentSum(cent, nodeCnt2[y]) + getCentSum(father2[cent], nodeCnt2[y]);
    
            father2[x] = y; //y反过来变成x的父节点
            dfs2(y, x);
        }
    
        //复原操作
        newHeavySon[x] = down[x][0] = heavySon[x];
        father2[x] = father[x];
        for(int j = 1; j <= depth; j++)
        {
            down[x][j] = down[down[x][j-1]][j-1];
        }
        nodeCnt2[x] = nodeCnt[x];
    }
    
    
    int main()
    {
    #ifndef ONLINE_JUDGE
        freopen("centroid.in", "r", stdin);
        //freopen("centroid.out", "w", stdout);
    #endif
    
        scanf("%d", &T);
        while(T--)
        {
            memset(head, 0, sizeof(head));
            memset(heavySon, 0, sizeof(heavySon));
            memset(father2, 0, sizeof(father2));
            memset(father, 0, sizeof(father));
    
            cnt = 0; //边的编号
            ans = 0;
    
            scanf("%d", &n);
            for(int i = 1; i < n; i++)
            {
                int x, y;
                scanf("%d %d", &x, &y);
                add(x, y);
                add(y, x);
            }
    
            dfs(1, 0);
    
            memcpy(nodeCnt2, nodeCnt, sizeof(nodeCnt2));
            memcpy(newHeavySon, heavySon, sizeof(newHeavySon));
            memcpy(father2, father, sizeof(father2));
    
            dfs2(1, 0);
    
            cout << ans << endl;
        }
    
        return 0;
    }

> ====================================  
> 了解信息学奥赛请加微信307591841或QQ群581357582