记录编号	457220	评测结果	WAWWWWWWWA
题目名称	2837.wcg树	最终得分	20
用户昵称	FoolMike	是否通过	未通过
代码语言	C++	运行时间	0.201 s
提交时间	2017-10-07 08:41:29	内存使用	5.84 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){
		for (int i=0;i<x.size();i++) sort(v[x[i]].begin(),v[x[i]].end());
		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=fa[x[i]];
			son[v]--;
			if (!son[v]) y.push_back(v);
		}
		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;
}