「POJ-1655」Balancing Act（树形DP）

发表于 | 分类于 ，

「POJ-1655」Balancing Act
树形DP，树的重心（质心）

题意

树的重心（质心）。对于一棵n个节点的无根树，找到一个点，使得把树变成以该点为根的有根树时，最大子树的节点最小。

解法

先任选一个节点作为根，把无根树变成有根树，然后设d(i)表示以i为根的子树的节点个数。不难发现$d(i)=\sum_{j∈s(i)}d(j)+1$ 。删除节点i后，节点i的子树中最大有max{d(j)}个节点，i的“上方子树”中有n-d(i)个节点。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int maxn=2e4+10;
const int inf=0x3f3f3f3f;
int d[maxn],N,minNode,minBalance;
vector<int> tree[maxn];

void dfs(int node,int father)
{
    d[node]=1;
    int maxSubTree=0;
    for(int i=0;i<tree[node].size();i++)
    {
        int son=tree[node][i];
        if(son!=father)
        {
            dfs(son,node);
            d[node]+=d[son];
            maxSubTree=max(maxSubTree,d[son]);
        }
    }
    maxSubTree=max(maxSubTree,N-d[node]);
    if(maxSubTree<minBalance)
    {
        minBalance=maxSubTree;
        minNode=node;
    }
}

int main()
{
    int t,u,v;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&N);
        for(int i=1;i<N;i++)
            tree[i].clear();
        for(int i=1;i<N;i++)
        {
            scanf("%d%d",&u,&v);
            tree[u].push_back(v);
            tree[v].push_back(u);
        }
        minNode=0;
        minBalance=inf;
        dfs(1,0);
        printf("%d %d\n",minNode,minBalance);
    }
}