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

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

题目

题目链接

题解

贪心，DFS。

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

所以重点转换为了计算以 u u 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;
}