Submission #223819

---

Source Code Expand

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;
typedef long long ll;

map<ll, int> memo;
int solve(int u, int p, const vector< vector<int> > &conn){
	const ll key = (static_cast<ll>(u) << 32) | p;
	map<ll, int>::iterator it = memo.find(key);
	if(it != memo.end()){ return it->second; }
	int sum = 1;
	for(int i = 0; i < conn[u].size(); ++i){
		const int v = conn[u][i];
		if(v == p){ continue; }
		sum += solve(v, u, conn);
	}
	memo.insert(make_pair(key, sum));
	return sum;
}

int main(){
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	vector< vector<int> > conn(n);
	for(int i = 1; i < n; ++i){
		int p;
		cin >> p;
		conn[i].push_back(p);
		conn[p].push_back(i);
	}
	for(int u = 0; u < n; ++u){
		int answer = 0;
		for(int i = 0; i < conn[u].size(); ++i){
			const int v = conn[u][i];
			answer = max(answer, solve(v, u, conn));
		}
		cout << answer << "\n";
	}
	return 0;
}

Submission Info

Judge Result