[蓝桥杯 2021 省 A] 左孩子右兄弟_蓝桥杯 左孩子右兄弟

一、问题描述

P8744 [蓝桥杯 2021 省 A] 左孩子右兄弟

二、问题简析

2.1 左孩子右兄弟

首先，我们要了解怎么通过“左孩子右兄弟”表示法将多叉树转化为二叉树：对于一棵多叉树，一个父节点有多个子节点，将第一个子节点作为父节点的左孩子，并与父节点相连；将剩余的子节点作为左孩子的右兄弟，并用边与左孩子相连（不是父节点）；处理完所有子节点后，再按一样的规则处理其余父节点。

以该多叉树为例：

处理子节点：

以 1 为根节点“拉一下”二叉树：

注意： 多叉树中根节点的子节点并不一定按图所示的顺序排列，更准确地说，是无序的，也就是说左孩子和右兄弟的选择是任意的。

2.2 树状dp

设 $d{p}_i=$ 以 $i$ 为根节点的二叉树的高度；$A_i.size=$ 原多叉树中根节点 $i$ 的子节点个数；$j\in A_i$ 为根节点 $i$ 的所有子节点。
假设在原多叉树中，根节点 $i$ 的子节点都是叶节点，即子节点没有子节点。结合上图，就是没有节点 6。显然，用“左孩子右兄弟”转化后，$d{p}_i$ 仅取决于 $i$ 的子节点的个数，即 $d{p}_i=A_i.size$。
在上文的基础上，假设子节点不再是叶节点，即子节点有子节点。结合上图，就是考虑节点 6。从贪心的角度，为了使二叉树最高，肯定要尽可能“延长”树，即最高的子树放在最下面。本例中，就是把节点 2 放在最下面，因为以 2 为根节点的子树高度为 $1$，其余子树都为 $0$。贪心地处理后，最大高度就是根节点 $i$ 的子节点个数 + 子树的最大高度。

总结一下，

$$d{p}_i=A_i.size+max(d{p}_j|j\in A_i)$$

---

三、AC代码

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int quickin(void)
{
	int ret = 0;
	bool flag = false;
	char ch = getchar();
	while (ch < '0' || ch > '9')
	{
		if (ch == '-')    flag = true;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9' && ch != EOF)
	{
		ret = ret * 10 + ch - '0';
		ch = getchar();
	}
	if (flag)    ret = -ret;
	return ret;
}

const int MAX = 1e5 + 3;
int N, dp[MAX];
vector<int> A[MAX];

void dfs(int x)
{
	vector<int> B = A[x];
	for (int i = 0; i < B.size(); i++)
	{
		dfs(B[i]);
		dp[x] = max(dp[x], dp[B[i]]);
	}
	dp[x] += B.size();
}

int main()
{
	#ifdef LOCAL
	freopen("test.in", "r", stdin);
	#endif
	
	N = quickin();
	for (int i = 2; i <= N; i++)
	{
		int a = quickin();
		A[a].push_back(i);
	}
	
	dfs(1);
	cout << dp[1] << endl;
	
	return 0;
}
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

---

完