e59a37721489491abab0ba3e0ff3c132.png

一道将多叉数转换为二叉树的题。

具体方法,我们可以利用vector动态存储每个节点的儿子

我们最后要的是什么,是他的儿子层数和与他并列的兄弟层数。我们用max来找每个从不同的儿子节点延伸的层数的最大值,然后再加上我兄弟的数量。并在一起就是我们要求的最大层数。

代码:


#include<bits/stdc++.h>
using namespace std;
int n;
vector<vector<int>> num(100005);
int dfs(int x)
{
	int maxnum=0;
	int i;
	for(i=0;i<num[x].size();i++)
	{
		maxnum=max(maxnum,dfs(num[x][i]));
	} 
	return maxnum+num[x].size();
}
int main()
{
	cin>>n;
	int i;
	int k;
	for(i=2;i<=n;i++)
	{
		cin>>k;
		num[k].push_back(i);
	}
	cout<<dfs(1);
	
}