Submission #1321481

---

Source Code Expand

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,x,n) for(int i=x; i<(n); i++)
#define rrep(i,n) for(int i=(n)-1; i>=0; i--)
#define all(X) (X).begin(),(X).end()
#define X first
#define Y second
#define pb push_back
#define eb emplace_back

using namespace std;
typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

template<class A, size_t N, class T> void Fill(A (&a)[N], const T &v){ fill( (T*)a, (T*)(a+N), v ); }

const ll INF = 0x3fffffff;


int main(){
	//ios_base::sync_with_stdio(0);
	ll N, ans=0;
	vector<int> child[100005];
	int a[100005]={};

	cin >> N;
	rep(i,N-1){
		cin >> a[i+2];
		child[a[i+2]].push_back(i+2);
	}

	queue<int> que;
	rep(i,N-1) if( child[i+2].empty() ) que.push(i+2);

	vector<int> v[100005];
	while( !que.empty() ){
		int i = que.front(); que.pop();
		int p = a[i];
		int depth = 0;
		if( v[i].empty() ) depth = 1;
		else{
			int s = v[i].size();
			sort( all(v[i]) );
			rep(j,s){
				chmax( depth, s-j + v[i][j] );
			}
		}
		v[p].push_back( depth );
		if( v[p].size() == child[p].size() ){
			que.push( p );
		}
	}

	ans = v[0][0] - 1;
	cout << ans << endl;

	return 0;
}

Submission Info

Judge Result