左孩子右兄弟（2023寒假每日一题 18）

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

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

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

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

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

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

例如如下的多叉树：

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

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

输入格式
输入的第一行包含一个整数 $N$ 。
以下 $N-1$ 行，每行包含一个整数，依次表示 $2$ 至 $N$ 号结点的父结点编号。

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

数据范围
对于 $30\%$ 的评测用例，$1\le N\le 20$ ； 对于所有评测用例，$1\le N\le 10^5$ 。

输入样例：

5
1
1
1
2
1
2
3
4
5

输出样例：

4
1

---

#include
#include

using namespace std;

const int N = 100010;

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

void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx++; 
}

int dfs(int u){
    
    int cnt = 0, hmax = 0;
    for(int i = h[u]; ~i; i = ne[i]){
        int j = e[i];
        hmax = max(hmax, dfs(j));
        cnt++;
    }
    return cnt + hmax;
}

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