【题解】左孩子右孩子

题目：左孩子右兄弟

题意:

题意很简单，对于每个结点做这样的操作：

选任意顺序将所有子节点中任选作为左结点，将该结点的兄弟结点依次在右侧连接，最后形成一个二叉树。

要我们求出一颗给定树改为二叉树后最大的高度为多少。

思路：

• 由于父节点不能改变，所以得到的二叉树根节点也还是1
• 假设以1为父节点的所有子节点中孩子结点最多的那个结点为x
• 显然我们需要将x结点放在他所有兄弟结点的最下面
• 设size[i]表示以i为父节点的结点数，length[x]表示以结点x为根节点的树的高度
• 此时高度就变为size[1]+length[x]
• 于是问题变为去寻找以x为根节点的二叉树的高度，而这显然与寻找1为根节点的树的高度相同，于是考虑递归dfs
• vector中存放的是以i为父节点的所有结点，p[k] [i]是以k为父节点的第i个结点

代码：

#include<cmath>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const ll N = 100005;

vector<int>p[N];
int dfs(int k)
{
    if (p[k].size() == 0)return 0;
    int maxx = 0;
    for (int i = 0; i < p[k].size(); ++i)
        maxx = max(maxx, dfs(p[k][i]));
    return maxx+p[k].size();
}
int main()
{
    int n;
    cin >> n;
    for (int i = 2; i <= n; ++i)
    {
        int a; cin >> a;
        p[a].push_back(i);
    }
    cout<<dfs(1);
    return 0;
}

PS：

• 链式前向星存图，好处在于图的起点终点清晰，很容易获得思路。劣处是无法直接获取该节点有多少子节点，需要提前处理，这里用b[i]表示i的子节点数量。总体而言能用vector简单做还是选择vector更好。
• 树是有向边，只需要add(x,y)一次就可以

#include<cmath>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const ll N = 100005;
int head[N ], to[N ],nex[N ],cnt,b[N];
void add(int x, int y)
{
	to[++cnt] = y;
	nex[cnt] = head[x];
	head[x] = cnt;
}
int dfs(int x,int y)
{
	int maxx = 0;
	for (int i = head[x]; i != 0; i=nex[i])
	{
		if (to[i] == y)continue;
		maxx = max(maxx, dfs(to[i],x));
	}
	return maxx+b[x];
}
int main()
{
	int n;
	cin >> n;
	int a;
	for (int i = 2; i <= n; ++i)
	{
		cin >> a;
		add(a, i);
		b[a]++;
	}
	cout<<dfs(1, 0);
	return 0;
}