方法一:深搜
对于节点 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分
42 人评分
C语言训练-列出最简真分数序列* (C语言代码)浏览:505 |
printf基础练习2 (C语言代码)浏览:305 |
1025题解浏览:736 |
C语言程序设计教程(第三版)课后习题10.2 (C语言代码)浏览:1460 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:1068 |
链表数据求和操作 (C语言代码)浏览:942 |
C语言程序设计教程(第三版)课后习题12.3 (C语言代码)浏览:543 |
【出圈】 (C++代码)简单循环浏览:631 |
【偶数求和】 (C语言代码)浏览:435 |
C二级辅导-阶乘数列 (C语言代码)浏览:1768 |