2606: 蓝桥杯2021年第十二届省赛真题-左孩子右兄弟（C++）

方法一：深搜

    对于节点 i，在其子节点中找出：令该节点作为根节点时可以使高度最大的节点 j

    令节点 j 作为 i 的子节点中最后一个出现的节点，可使高度达到最大。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
 
int n, tmp;
vector<int> mp[MAXN];
 
int dfs(int idx) {
    int sz = mp[idx].size();
    int ans = 0;
    for (int i = 0; i < sz; i++) {
        ans = max(ans, dfs(mp[idx][i]));
    }
    return ans + sz;
}
 
int main() {
    cin >> n;
    for (int i = 2; i <= n; i++) {
        cin >> tmp;
        mp[tmp].push_back(i);
    }
    cout << dfs(1) << endl;
    return 0;
}

方法二：动态规划

    用数组 s[i] 表示节点 i 的子节点个数，用数组 f[i] 表示节点 i 的父节点，dp[i] 表示当节点 i 作为根节点时的最大高度

    可以推断出如下状态转移方程：

        dp[f[i]] = max(dp[f[i]], s[f[i]] + dp[i]);

    由于子节点一定比父节点的编号大，所以对节点编号逆向遍历即可。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
 
int n, tmp;
int s[MAXN], f[MAXN], dp[MAXN];
 
int main() {
    cin >> n;
    for (int i = 2; i <= n; i++) {
        cin >> tmp;
        f[i] = tmp;
        s[tmp]++;
    }
     
    for (int i = n; i > 1; i--) {
        int fa = f[i];
        dp[fa] = max(dp[fa], s[fa] + dp[i]);
    }
    cout << dp[1] << endl;
    return 0;
}