3422. 左孩子右兄弟

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

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

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

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

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

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

例如如下的多叉树:

QQ截图20210426100551.png

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

QQ截图20210426100638.png

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

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

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

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

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

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

思路 :文章来源地址https://uudwc.com/A/XE5Z

  • 求树的高度从最下往上看动态规划,需要递归访问子树
  • 状态表示: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]);
}

原文地址:https://blog.csdn.net/m0_51448653/article/details/128751630

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请联系站长进行投诉反馈,一经查实,立即删除!

h
上一篇 2023年06月17日 10:41
树莓派链接蓝牙键盘
下一篇 2023年06月17日 10:42