3422. 左孩子右兄弟_左孩子右兄弟查询节点

对于一棵多叉树，我们可以通过 “左孩子右兄弟” 表示法，将其转化成一棵二叉树。

如果我们认为每个结点的子结点是无序的，那么得到的二叉树可能不唯一。

换句话说，每个结点可以选任意子结点作为左孩子，并按任意顺序连接右兄弟。

给定一棵包含 N 个结点的多叉树，结点从 1 至 N 编号，其中 1 号结点是根，每个结点的父结点的编号比自己的编号小。

请你计算其通过 “左孩子右兄弟” 表示法转化成的二叉树，高度最高是多少。

注：只有根结点这一个结点的树高度为 0。

例如如下的多叉树：

可能有以下 3 种 (这里只列出 3 种，并不是全部) 不同的 “左孩子右兄弟”表示：

其中最后一种高度最高，为 4。

输入格式
输入的第一行包含一个整数 N。

以下 N−1 行，每行包含一个整数，依次表示 2 至 N 号结点的父结点编号。

输出格式
输出一个整数表示答案。

数据范围
对于 30% 的评测用例，1≤N≤20；
对于所有评测用例，1≤N≤105。

输入样例：
5
1
1
1
2
输出样例：
4

思路 ：

• 求树的高度，从最下往上看，动态规划，需要递归访问子树
• 状态表示：f[u]表示以u为根结点的子树的最大高度
• 状态计算：f[u] = max(f[u], f[v] + num[u])
  即，当前树的高度等于它 与 其子树的高度+以这个节点为根的儿子结点数量 取max

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;

int n;
int e[N], ne[N], h[N], idx;
int num[N], f[N];

void add(int u, int v) {
    e[idx] = v; ne[idx] = h[u]; h[u] = idx ++ ;
}
void dfs(int u) {
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        dfs(j);
        f[u] = max(f[u], f[j] + num[u]);
    }
}

int main() {
    scanf("%d", &n);
    memset(h, -1, sizeof h);
    for (int i = 2, x; i <= n; ++ i) {
        scanf("%d", &x);
        add(x, i);
        num[x] ++ ;
    }
    dfs(1);
    printf("%d", f[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