2021年蓝桥杯A组省赛-左children右sibling

CXXX有毛病？“左孩子右兄弟”字眼很敏感吗？？？

题目

题目链接

题解

贪心，DFS。

以 $u$ 为根的子树选择包含节点最多的以 $v$ 为根的子树作为最后连接的右兄弟能保证树向下延展的最多。

所以重点转换为了计算以 $u$ 每个子结点为根的子树中包含节点最大的个数，递归计算每个子树的节点数（不含根节点），每棵子树能构成的最深深度为其直接子节点数量+能构造出来最深的二叉树的深度（并不是全部节点数量）

一开始想的是每次都以最大的子树向下扩展，但是写代码的时候想成了以直接子结点最多的子树向下扩展。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int n;
int f[N];
vector <int> v[N];
void dfs (int x) {
int res = 0;
f[x] = v[x].size();
for (int i = 0;i < v[x].size();i ++) {
int t = v[x][i];
dfs (t);
res = max (f[t], res);
}
f[x] += res;
}
int main()
{
cin >> n ;
for (int i = 2;i <= n;i ++)	{
int x;
cin >> x;
v[x].push_back (i);
}
dfs (1);
cout << f[1] << endl;
return 0;
}

最后

以上就是搞怪朋友为你收集整理的2021年蓝桥杯A组省赛-左children右sibling的全部内容，希望文章能够帮你解决2021年蓝桥杯A组省赛-左children右sibling所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。