摘要
Title: 3422. 左孩子右兄弟
Tag: 树形dp
Memory Limit: 64 MB
Time Limit: 1000 ms

3422. 左孩子右兄弟

题意

第十二届蓝桥杯省赛第一场C++A/C组,第十二届蓝桥杯省赛第一场JAVAA/C组

对于一棵多叉树，我们可以通过 “左孩子右兄弟” 表示法，将其转化成一棵二叉树。
如果我们认为每个结点的子结点是无序的，那么得到的二叉树可能不唯一。
换句话说，每个结点可以选任意子结点作为左孩子，并按任意顺序连接右兄弟。
给定一棵包含 N 个结点的多叉树，结点从 1 至 N 编号，其中 1号结点是根，每个结点的父结点的编号比自己的编号小。
请你计算其通过 “左孩子右兄弟” 表示法转化成的二叉树，高度最高是多少。
注：只有根结点这一个结点的树高度为 0
思路

树形dp裸题
$dp[u]=max(dp[u],dp[j]+num[u])$
num[u]表示的是以u为根节点的子节点个数
当前树的高度等于它与其 子树高度 + 以这个节点为根的儿子结点数之和 取max

代码

/*
* @Author: NEFU AB-IN
* @Date: 2023-01-18 12:22:11
* @FilePath: \Acwing\3422\3422.cpp
* @LastEditTime: 2023-01-18 12:34:51
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#undef int

#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;

int n;
vector<int> g[N];
int dp[N], num[N];

void dfs(int u)
{
    for (auto v : g[u])
    {
        dfs(v);
        dp[u] = max(dp[u], dp[v] + num[u]);
    }
}

signed main()
{
    IOS;
    cin >> n;
    for (int i = 2; i <= n; ++i)
    {
        int x;
        cin >> x;
        g[x].push_back(i);
        num[x]++;
    }
    dfs(1);
    cout << dp[1];
    return 0;
}

3422. 左孩子右兄弟

题意

思路

代码