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

5772 阅读 0 评论 3810 点赞

我是靠谱客的博主搞怪朋友，这篇文章主要介绍2021年蓝桥杯A组省赛-左children右sibling，现在分享给大家，希望可以做个参考。

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

题目

题目链接

题解

贪心，DFS。

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

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

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

代码

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#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;
}