Submission #1438462

---

Source Code Expand

#include <iostream>
#include <map>
#include <vector>
#include <cstring>
#include <utility>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <string>
#include <stack>
#include <set>
#include <deque>
#define mp make_pair
using namespace std;
int n,a[100005],maxi,in[100005],v[100005];
vector <int> ve[100005];
map <int,int> ma;
int main(){
	cin>>n;
	v[100002]=-1;
	for (int i=2;i<=n;i++){
		cin>>a[i];
		in[a[i]]++;
	}
	queue <int> que;
	for (int i=1;i<=n;i++){
		if (in[i]==0) que.push(i); 
		if (in[i]==0) ve[i].push_back(-1); 
	}
	while (!que.empty()){
		int p=que.front();
		que.pop();
		ma.clear();
		maxi=0;
		for (int i=0;i<ve[p].size();i++) ma[ve[p][i]]++;
		for (map<int,int>::iterator it=ma.begin();it!=ma.end();it++){
			maxi=max(maxi,it->second+it->first);
		}
		int extr=0;
		for (map<int,int>::iterator it=ma.begin();it!=ma.end();it++){
			if (it->first+it->second==maxi) extr++;
		}
		extr--;
		maxi+=extr;
		v[p]=maxi;
		in[a[p]]--;
		if (in[a[p]]==0) que.push(a[p]); 
		ve[a[p]].push_back(v[p]); 
	}
	cout<<v[1];
	return 0;
}

Submission Info

Judge Result