poj 1655 Balancing Act 【树的重心】

爱被打了一巴掌 2022-09-21 01:03 161阅读 0赞

知识点：树的重心

定义：以这个点为根，那么所有的子树（不算整个树自身）的大小都不超过整个树大小的一半。

性质：

性质 1 ：树中所有点到某个点的距离和中，到重心的距离和是最小的，如果有两个距离和，他们的距离和一样。

性质 2 ：把两棵树通过某一点相连得到一颗新的树，新的树的重心必然在连接原来两棵树重心的路径上。

性质 3 ：一棵树添加或者删除一个节点，树的重心最多只移动一条边的位置。

题目：[poj 1655 Balancing Act][]

题意：给出一颗树，求树的重心点以及重心点删除后中的最大子树。

分析：

根据性质 1 ，我们容易想到枚举每个点作为 root ，然后求一次其子树的点和，然后每次找出一个最大的子树，最后最小的子树既为重心带你，O（n^2）的时间，TEL

一个删除后得到的子树，要么是从子节点过来的，要么是从父节点过来的，子节点的子树节点和的我们可以通过一次简单的dfs维护求得son【child】。

而父亲点过来的为总的节点数 N - son【father】 - 1

那么事情就变的简单了，我们只要维护dp【father】 = max（son【child】，N - son【father】-1）

代码：

#include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <cmath>
    #include <queue>
    #include <vector>
    #include <map>
    #include <set>
    #include <string>
    using namespace std;
    #define Del(a,b) memset(a,b,sizeof(a))
    const int N = 20100;
    vector<int> v[N];
    int vis[N],dp[N],son[N];
    int ans,asize;
    int n;
    void DFS(int s)
    {
        vis[s] = 1;
        son[s] = 0;
        int blance = 0;
        int size = v[s].size();
        for (int j = 0;j < size;j++)
        {
            int u = v[s][j];
            if (vis[u]) continue;
            DFS(u);
            son[s] += son[u]+1;
            blance = max(blance,son[u]+1);
        }
        blance = max(blance,n - son[s] - 1);
        if (blance < asize || blance == asize && s < ans)
            ans = s,asize = blance;
    }
    int main()
    {
        int T;
        scanf("%d",&T);
        while(T--)
        {
    
            scanf("%d",&n);
            for(int i=0;i<n-1;i++)
            {
                int x,y;
                scanf("%d%d",&x,&y);
                v[x].push_back(y);
                v[y].push_back(x);
            }
            ans=1;
            Del(vis,0);Del(son,0);
            Del(dp,0);
            asize=0x3f3f3f3f;
            DFS(1);
            printf("%d %d\n",ans,asize);
            for(int i=0;i<=n;i++)
                v[i].clear();
        }
        return 0;
    }

[poj 1655 Balancing Act]: http://poj.org/problem?id=1655