题目描述
对于一棵多叉树,我们可以通过 “左孩子右兄弟” 表示法,将其转化成一棵二叉树。
如果我们认为每个结点的子结点是无序的,那么得到的二叉树可能不唯一。
换句话说,每个结点可以选任意子结点作为左孩子,并按任意顺序连接右兄弟。
给定一棵包含 $N$ 个结点的多叉树,结点从 $1$ 至 $N$ 编号,其中 $1$ 号结点是根,每个结点的父结点的编号比自己的编号小。
请你计算其通过 “左孩子右兄弟” 表示法转化成的二叉树,高度最高是多少。
注:只有根结点这一个结点的树高度为 $0$。
例如如下的多叉树:
可能有以下 $3$ 种 (这里只列出 $3$ 种,并不是全部) 不同的 “左孩子右兄弟”表示:
其中最后一种高度最高,为 $4$。
输入格式
输入的第一行包含一个整数 $N$。
以下 $N−1$ 行,每行包含一个整数,依次表示 $2$ 至 $N$ 号结点的父结点编号。
输出格式
输出一个整数表示答案。
数据范围
对于 $30\\%$ 的评测用例,$1 ≤ N ≤ 20$;
对于所有评测用例,$1 ≤ N ≤ 10^5$。
输入样例:
5
1
1
1
2
输出样例:
4
解题思路
题目大意:对于一颗根节点为 $1$ 的树,可以使任意节点的兄弟节点连同这个节点的一个子节点形成两棵子树。问经过任意次操作后使得这棵树变成一颗二叉树,这棵二叉树的深度最大是多少?
首先根据输入在父节点和这个节点之间连一条边,以完成建图操作。
不难想到,每棵子树的深度只跟这棵子树内部有关,与其它节点没有关系。因此考虑分治算法求解。
对于一个节点,遍历它的所有子节点,进行分治求解;特别地,若一个节点没有子节点(叶子结点),则这棵子树的深度为 $0$。
观察样例可发现,某个子节点的多个子节点可连成一条链,这棵子树内部深度相当于链的长度加上链末端子树的深度。我们可用树形 $\textsf {dp}$ 分别对每一子节点分治求出其深度,再由贪心算法知可把深度最大的子节点放在链末端。因此,即当前节点有 $cnt$ 个子节点,其中子节点深度最大值为 $mx$,那么以当前节点为代表的子树深度为 $cnt + mx$。
AC Code
#include <cstdio>
#define N 100005
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
int n, x, tot, head[N], nxt[N], ver[N];
void insert (int x, int y) // 加边建图
{
ver[++ tot] = y, nxt[tot] = head[x], head[x] = tot;
return ;
}
int dfs (int x) // 树形 dp(分治)
{
int mx = 0, cnt = 0, now;
for (int i = head[x], y; i; i = nxt[i])
{
now = dfs (y = ver[i]), mx = max (mx, now), cnt ++;
}
return mx + cnt;
}
int main ()
{
scanf ("%d", &n);
for (int i = 2; i <= n; i ++)
{
scanf ("%d", &x), insert (x, i);
}
printf ("%d", dfs (1));
return 0;
}
感谢观看!
密码碎片:bene
$$\href {/blog/content/29204/} {\color {Lime} {【寒假每日一题】题解}}$$
AcWing【集日历瓜分10000AC币活动】赠送2月日历!
什么叫“右兄弟”?
哦,不对。我知道了。题目没有给出右兄弟的概念。
简单来说,比如样例,如果 2 还有个子节点 6,那么选择 3 作为 1 的左孩子的时候, 4 应该怎么连?
同时,2 的 5 和 6 能动吗?把 4 接到 5 后面,在把 6 接到 4 后面,不就是条链?
我现在还觉得一定可以把这棵树变成一条链
不行。因为有可能有多颗子树不为叶子结点
?什么意思?
谁的子树?谁的叶子节点?是变完之后的叶子节点?还是初始状态的叶子节点?子树怎么会是叶子节点?叶子节点不是个点吗?子树不是个集合吗?
不行, 如果某个节点的子节点中有两个及以上的节点不是叶子节点就无法变成链。
(否则, 答案就直接是N - 1了)