Submission #1438849

---

Source Code Expand

#include <assert.h>
#include <ctype.h>
#include <errno.h>
#include <float.h>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <set>
#include <queue>
#include <limits>
#include <vector>
#include <deque>
#include <locale>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <wchar.h>
#include <wctype.h>
#include <algorithm>
#include <bitset>
#include <map>
#include <iomanip>
#include <ios>
#include <iostream>
#include <vector>
#include <cwchar>
#include <cwctype>
#define mp make_pair
#define fs first
#define se second
#define memset(a,t) memset(a,t,sizeof(a))
#define all(v) v.begin(),v.end()
#define eprintf(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define MN 0LL
#define Mx 200000005
#define Mn -Mx
#define MX 20000000000000005
using namespace std;
int readint(){
	char c;
	while(c=getchar(),(c<'0'||c>'9')&&c!='-');
	bool flag=(c=='-');
	if(flag)c=getchar();
	int x=0;
	while(c>='0'&&c<='9'){
		x=x*10+c-48;
		c=getchar();
	}
	return flag?-x:x;
}
inline string tos(int x){
	string s;
	while(x) s=(char)(x%10+'0')+s,x/=10;
	return s;
}
int n,ans;
int rem[1000005];
bool dead[1000005];
vector<int> v[1000005];
inline int dfs(int dp){
	if(rem[dp]) return rem[dp];
	dead[dp]=1;
	int res=0;
	vector<int> gss;
	for(int i=0;i<v[dp].size();i++){
		if(dead[v[dp][i]]) continue;
		int t=dfs(v[dp][i]);
		gss.push_back(t);
	}
	sort(gss.begin(),gss.end());
	for(int i=0;i<v[dp].size();i++){
		res=max(int(gss[i]+v[dp].size()-i-1),res);
	}
	res++;
	rem[dp]=res;
	return res;
}
int main(){
	ios_base::sync_with_stdio(false);
	int i,j,t;
	cin>>n;
	for(i=2;i<=n;i++){
		cin>>t;
//		if(i==a[i]) exit(41234);
		v[t].push_back(i);
	}
//	if(v[1].size()==0) exit(1);
	cout<<dfs(1)-1<<endl;
//	for(i=1;i<=n;i++) cout<<gs[i]<<" ";
//	cout<<endl;
	return 0;
}

Submission Info

Judge Result