poj 1655 Balancing Act 树的重心板题

缘起

树的重心(有的文章叫质心)是紫书中的树形DP的一个小节（树的重心也属于树形DP的内容）. 而且在 ACM算法日常 这个公众号中看到了, 但是~ 我特喵的竟然没看过! 所以赶紧找了紫书, 学习了一下, 还是蛮简单的~ poj 1655 Balancing Act

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
给你一棵N个节点的树（节点标号为1,...,N）,求它的重心. 如果存在多个, 输出标号最小的那一个.

【输入】
多样例. 第一行是样例数. 每个样例包含一个整数N（1 <= N <= 20,000）, 然后n-1行每行两个数, 表示树边.

【输出】
对每个样例输出重心以及它的平衡度.

【样例输入】
1
7
2 6
1 2
1 4
4 5
3 7
3 1

【样例输出】
1 2

【限制】
1s

做这道题目首先要明白什么是树的重心? 按照紫书的说法

1
2
对于一棵n个结点的无根树，找到一个点R，使得把树变成以该点为根的有根树时，最大子树的节点个数最小。 
换句话说，删除这个点R后最大连通块（一定是树）的节点个数（定义为R的平衡度）最小。

一图胜千言~

上图是一棵无根树.

ps: 这里多说一句，什么是有根树，什么是无根树. 所谓有根树就是不是无根树的树（废话~ 逃）.而无根树，即没有所谓的“父子”关系，而只有一些无向边。

回到正题，如果删掉节点4的话，则产生的森林由6-2-1-3-7 这棵树A和5这棵（单节点）树B构成. 则4的平衡度是5（因为A的节点个数是5）。但是如果删掉1的话, 则产生的森林由 2-6、3-7、4-5 三棵树构成. 所以1的平衡度是2（因为子树中的最大节点数是2）， 所以不难知道上图中的树的重心是1, 平衡度是2，就本题而言就要输出1 2了.

那么树的重心的算法是什么呢? 很简单, 一次dfs就行了。

首先, 因为是一棵无根树, 很不好, 所以我们首先选择任意一点（譬如1）作为树的根, 将树转换为有根树。

1
令 d[i] 是以i为根节点的子树的节点个数. 则通过一次从根节点入手的dfs, 很容易求出所有节点的dp值.

那么我怎么维护出树的重心呢? 当我们dfs从一个顶点i退出的时候, 我们自然知道了i的所有子节点son1,…,sonk的d值. 所以如果删除i的话, 则产生的森林将由大小分别为{n-d[i],d[son1],…,d[sonk]}这k+1棵子树构成. 所以我们就很容易维护出重心以及重心的平衡度了.

说了这么多, 可以愉快的搞出一个树的重心的O(n)板子——顺便说一下，这里的思想对于带权树也是适用的~ 只不过节点个数是一种特殊的权——每个节点的权值为1而已. 

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
//#define LOCAL
const int maxn = 20005, inf = 0x3f3f3f3f;
int n, cnt, head[maxn],pos,ans; // pos是重心, ans是重心的平衡度
struct Arc
{
	int from,to,nxt;
}g[maxn<<1];

void addarc(int from,int to)
{
	g[cnt].from = from, g[cnt].to = to, g[cnt].nxt = head[from];
	head[from] = cnt++;
}

int dfs(int cur, int fa) // cur是当前节点, fa是父节点, fa->cur是树边
{
	int ret = 1, b = 0; // cur自己算一个节点, b是cur的平衡度
	for (int h = head[cur],to,son; ~h; h = g[h].nxt)
	{
		to = g[h].to;
		if (to==fa) // 返祖边是不允许的
		{
			continue;
		}
		son = dfs(to,cur); // 子树节点的个数
		ret+=son; // 维护cur为根的子树的节点个数
		b = max(b, son); // 维护cur的平衡度
	}
	b = max(b, n-ret); // 维护cur的平衡度
	if (b<ans || b==ans && cur<pos) // 如果真的小, 则一定要更新, 或者平衡度 相等, 但是标号更小的话, 则也要更新
	{
		ans = b;
		pos = cur;
	}
	return ret;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	int kase;
	scanf("%d", &kase);
	while(kase--)
	{
		memset(head,-1,sizeof(head));
		pos = cnt = 0;
		ans = inf;
		scanf("%d", &n);
		int nn = n;
		while(--nn)
		{
			int a,b;
			scanf("%d%d", &a, &b);
			addarc(a,b);
			addarc(b,a); // 无向边
		}
		dfs(1,0); // 随便选一个点作为根(例如1)
		printf("%d %d\n", pos, ans);
	}
	return 0;
}

ac情况

Status Accepted
Time 32ms
Memory 664kB
Length 1281
Lang C++
Submitted 2019-11-06 09:48:03
Shared
RemoteRunId 21025507