cf 686D Kay and Snowflake 树的重心

缘起

继续学习树的重心~ cf 686D Kay and Snowflake

分析

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
给你一棵n个顶点的有根树. 树根假设是1(顶点标号1~n). 然后q个询问. 每个询问就是询问每棵子树的重心.

【输入】
只需要处理一组数据, 第一行是n和q, 2 ≤ n ≤ 300 000, 1 ≤ q ≤ 300 000
然后第二行是n-1个整数, 表明第i个顶点(2<=i<=n)的父节点是哪个.
然后是q行,每行一个整数, 表明我们询问q节点表示的子树的重心。

【输出】
对每个询问, 输出子树的重心，如果有多个, 输出任意一个即可~

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

【样例输出】
3
2
3
6

【限制】
3s 256MB

【是否接受特判】
Yes

【hint】
本题给出的树的样子是

和【1】相比, 【1】仅仅求的是一个重心, 但是本题要求多棵子树的重心. 如果暴力使用【1】的板子求所有子树的重心的话, 肯定T. 正（优）确（雅）的方法应该是随着dfs, 自然的维护所需要的信息

当然，本题依旧是从dfs的角度来做. 所以我们自然要考虑的事情是, 当求出了一个顶点的所有子节点的重心之后, 我们该怎么找当前子树的重心. 如果能找到, 那么我们就算是顺利的解决了这道题目.

如上图所示, 我们已经从R的子节点A、B、C的递归中退出了. 来到了R的递归层. 则根据【1】中的板子, 我们是可以知道A的子树的大小（记做sz(A), 以此类推）,sz(B),sz(C)的，并且我们已经求出了TA、TB、TC的重心分别为posA、posB、posC. 我们假设 sz(A)>sz(B)>sz(C)

现在询问R为根的子树的重心. 注意到本题比较猥（阴）琐（险）的一点是——随意输出一个重心即可~

按照重心的定义, R的重心一定在以A为根的子树（记做TA，以此类推），TB或者TC或者就是R本身.

那么凭直觉（其实是树的重心的性质, 参见后记） 我们显然知道R的重心一定在posA–>R 这条链上. 所以我们可以直接沿着子问题TA的解——posA往R跳, 直至到R. 求出R的重心即可.

注意！这里本题的树的重心的定义和紫书P434的定义不一样, 所以我们完全可以在posA–R这条路上找到了重心就不再找了.

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
70
71
72
73
74
75
76
77
78
79
//#include "stdafx.h"
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
//#define LOCAL
const int maxn = 300005,inf = 0x3f3f3f3f;
int n,q, fa[maxn],sz[maxn],pos[maxn],mmaxsz[maxn], mmaxszid[maxn]; // 显然, 本题使用孩子双亲表示法(child向量+fa数组)存储树是恰当的, sz[i]表示以i为顶点的子树的节点个数,pos[i]表示以i为根节点的子树的重心, mmaxsz[i]表示以i为节点的树的最茂盛的子树大小, mmaxszid[i]是以i为根的树的最茂盛的那棵子树的根节点编号
vector<int> child[maxn];
typedef vector<int>::iterator vit;

int dfs(int cur) // 函数返回cur为根的子树的大小并且记录到sz[cur]中去,用于给kk方法使用, 并且维护mmaxsz和mmaxszid, 也是供kk使用
{
	for (vit x = child[cur].begin(); x!=child[cur].end(); x++)
	{
		int t = dfs(*x);
		if (mmaxsz[cur]<t)
		{
			mmaxsz[cur] = t;
			mmaxszid[cur] = *x;
		}
		sz[cur]+=t;
	}
	return sz[cur];
}

inline int cal(int x, int y) // 计算x作为y的子节点, 在y为根的子树中的平衡度
{
	return max(mmaxsz[x], sz[y]-sz[x]);
}

inline int kk(int cur) // 函数返回cur为根节点的子树的重心
{
	if (pos[cur]) // 记忆化处理
	{
		return pos[cur];
	}
	pos[cur] = cur; // 先默认是自己（叶子节点就真是自己了）
	if (mmaxszid[cur]) // 最茂盛的子树
	{
		kk(mmaxszid[cur]); // 求解子问题
		int w = pos[mmaxszid[cur]]; // 求出最茂盛的子树的重心
		while (w!=cur) // 从最茂盛的子树的重心开始往cur跳, 找出cur的重心
		{
			if (2*cal(w,cur)<=sz[cur]) // 如果满足了, 就不玩了
			{
				break;
			}
			w = fa[w];
		}
		pos[cur] = w;
	}
	return pos[cur]; // 得到cur为根节点的子树的重心
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//	freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d%d", &n, &q);
	fa[1] = 0;
	for (int i = 2,pa;i<=n;i++)
	{
		scanf("%d",&pa); // pa是i的父亲
		fa[i] = pa;
		child[pa].push_back(i);
	}
	fill(sz+1,sz+n+1,1);
	dfs(1); // 为了方便, 这里先O(n)单纯预处理出所有子树的大小
	while(q--)
	{
		int qq;
		scanf("%d", &qq);
		printf("%d\n", kk(qq));
	}
	return 0;
}

ac情况

Status Accepted
Time 358ms
Memory 19980kB
Length 1644
Lang Microsoft Visual C++ 2017
Submitted 2019-11-06 17:58:18
Shared
RemoteRunId 64355275

后记

关于本题, 我还去查了树的重心的性质如下

  1. 删除重心后所得的所有子树，节点数不超过原树的1/2，一棵树最多有两个重心；

  2. 树中所有节点到重心的距离之和最小，如果有两个重心，那么他们距离之和相等；

  3. 两个树通过一条边合并，新的重心在原树两个重心的路径上；

  4. 树删除或添加一个叶子节点，重心最多只移动一条边；

参考

【1】https://yfsyfs.github.io/2019/11/06/poj-1655-Balancing-Act-%E6%A0%91%E7%9A%84%E9%87%8D%E5%BF%83%E6%9D%BF%E9%A2%98/