CodeRookie


私信TA

用户名:Shmily124

访问量:118296

签 名:

清风前烹茶对弈,明月下把酒言欢

等  级
排  名 15
经  验 21059
参赛次数 7
文章发表 39
年  龄 0
在职情况 学生
学  校 ZUA
专  业 计科

  自我简介:

悄悄地秃头,然后惊艳所有人?

方法一:深搜

    对于节点 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;
}


 

0.0分

40 人评分

  评论区

;//对于每个父节点,它的最大高度应为其子节点的最大高度加上子节点的总数
为啥啊一直这里没懂
2023-01-12 22:14:06
存节点的数组和存子节点数量的下标都不对应
2023-01-01 23:04:26
最后,是子节点一定比父节点的编号大吧?
2022-03-15 11:09:09
  • «
  • 1
  • »