记录编号	274941	评测结果	AAAAAAAAAA
题目名称	[Codeforces 685B] 树的重心	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	0.831 s
提交时间	2016-06-30 17:12:06	内存使用	17.46 MiB

#include<stdio.h>
int n,shu,first[500010],fa[500010],s[500010],g[500010],son[500010];
struct edge{int v,nx;}o[1000010];
void add(int u,int v){o[++shu].v=v,o[shu].nx=first[u],first[u]=shu;}
void dfs(int x){
	s[x]=1;
	for(int i=first[x];i;i=o[i].nx){
		dfs(o[i].v),s[x]+=s[o[i].v];
		if(s[o[i].v]>s[son[x]])son[x]=o[i].v;
	}
	if(!son[x])g[x]=x;
	else for(g[x]=g[son[x]];s[g[x]]*2<s[x];g[x]=fa[g[x]]);
}
int main(){
	freopen("kayandsnowflake.in","r",stdin);
	freopen("kayandsnowflake.out","w",stdout);
	scanf("%d",&n);
	for(int i=2;i<=n;++i)scanf("%d",&fa[i]),add(fa[i],i);
	dfs(1);
	for(int i=1;i<=n;++i)printf("%d\n",g[i]);
	//while(1);
}