AcWing 3422. 左孩子右兄弟(纯暴力全过版,超易懂)
原题链接
中等
作者:
o存
,
2025-04-01 09:28:22
· 广东
,
所有人可见
,
阅读 2
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
int a[100010];
int deep[100010];
int hmax;
int state[100010];
int used[100010];
int main()
{
int n;
cin >> n;
for (int i = 2; i <= n; i++)
{
cin >> a[i];
}
for (int i = 2; i <= n; i++)
{
state[a[i]]++;
}
for (int i = 2; i <= n; i++)
{
deep[i] = state[a[i]];
}
for (int i = n; i >= 2; i--)
{
if(used[i]==0)
{
int num = 0;
int j = i;
while (deep[j])
{
used[j]=1;
num += deep[j];
j = a[j];
}
hmax = max(num, hmax);
}
}
printf("%d", hmax);
}