题目大意

给定一棵节点个数为 $N$ 的多叉树，求其通过“左孩子右兄弟”表示法转化成的二叉树，高度最高是多少。

解决思路

首先分辨出此题目是树状DP，并了解“左孩子右兄弟”表示法的转换方式，便开始考虑DP的状态转移方程。

状态

由于每个节点由 $1$ 至 $N$ 编号，那么就使用 $dp_{k}$ 表示此时k号节点的目标状态（转化后二叉树的最高高度）。

转移

这里需要用到 贪心策略， 对于一个节点 $k$ , 它的子节点为 ${v_1,v_2,v_3,\dots,v_cnt}$, 那么使用贪心策略找到能作出贡献最大的的子节点 （$\max{v_1,v_2,v_3,\dots,v_cnt}$），再将其他的节点垫在它上面（ $\max{v_1,v_2,v_3,\dots,v_k} + cnt$）就行了。

目标状态

根节点编号为 $1$ ,所以整个算法的 目标状态 为 $dp_1$。

Code & 解析

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
long long n, x, dp[N];
vector<long long> v[N];          // 保存子节点 
void DP(long long x) {
  for (auto i : v[x]) {      
    DP(i);                       // 先找出以此节点为根的最大高度
    dp[x] = max(dp[x], dp[i]);   // 找出最能作出贡献的，将其放在最下面
  } dp[x] += v[x].size();        // 将其它的子节点叠在上面
}
int main() {
  cin >> n;
  for (int i = 2; i <= n; i++) {
    cin >> x; v[x].push_back(i); // 压入子节点
  } DP(1);                       // 从根节点开始访问
  cout << dp[1];                 // 输出最终状态
  return 0;
}