记录编号	457221	评测结果	AAAAAAAAAA
题目名称	2837.wcg树	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.740 s
提交时间	2017-10-07 08:45:31	内存使用	5.83 MiB

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e5+10;
int n,fa[N],son[N],tp[N],flag[N],C,cnt;
vector<int> v[N],x,y;
bool cmp(int x,int y){return v[x]<v[y];}
int main()
{
	freopen("wcgtree.in","r",stdin);
	freopen("wcgtree.out","w",stdout);
	scanf("%d",&n);
	for (int i=2;i<=n;i++) scanf("%d",&fa[i]),son[fa[i]]++;
	for (int i=1;i<=n;i++) if (!son[i]) x.push_back(i);
	while (1){
		sort(x.begin(),x.end(),cmp);
		tp[x[0]]=++C;
		for (int i=1;i<x.size();i++) tp[x[i]]=(v[x[i]]==v[x[i-1]]?C:++C);
		if (tp[1]) break;
		y.clear();
		for (int i=0;i<x.size();i++){
			int V=x[i],f=fa[V];
			son[f]--;
			v[f].push_back(tp[V]);
			if (!son[f]) y.push_back(f);
		}
		x=y;
	}
	for (int i=1;i<=n;i++)
		if (!flag[tp[i]]) flag[tp[i]]=++cnt;
	for (int i=1;i<=n;i++) printf("%d ",flag[tp[i]]);
	puts("");
	return 0;
}