1 条题解
-
0
设f[u]表示以u为根节点能够得到的最大高度,则取u的f值最大的子节点v,让这个子节点贡献f[v]的高度,其他子节点以及u本身各贡献1的高度即可。
核心代码
void dfs(int u) { int sz = g[u].size(); for (int i = 0; i < sz; i ++) { int v = g[u][i]; dfs(v); f[u] = f[u] > f[v] ? f[u] : f[v]; } f[u] += sz; } int main() { cin >> n; for (int i = 2; i <= n; i ++) { cin >> u; g[u].push_back(i); } dfs(1); cout << f[1]; return 0; }
- 1
信息
- ID
- 844
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- (无)
- 递交数
- 17
- 已通过
- 12
- 上传者