首页 > 代码库 > poj 1655 Balancing Act 【树的重心】

poj 1655 Balancing Act 【树的重心】

知识点:树的重心


定义:以这个点为根,那么所有的子树(不算整个树自身)的大小都不超过整个树大小的一半。


性质:

性质 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 【树的重心】