记录编号	274752	评测结果	AAAAAAAAAA
题目名称	[Codeforces 685B] 树的重心	最终得分	100
用户昵称	Satoshi	是否通过	通过
代码语言	C++	运行时间	4.490 s
提交时间	2016-06-29 17:05:16	内存使用	13.67 MiB

#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#define N 500010
using namespace std;
ifstream cin("kayandsnowflake.in");
ofstream cout("kayandsnowflake.out");
int P[N]={0};
int son[N]={0},size[N]={0};
int n;
vector<int> G[N];
int fa[N]={0};
bool check(int u,int v)
{
	return (size[u]-size[v])*2<=size[u]&&size[son[v]]*2<=size[u];
}
void DFS1(int u)
{
	int i,v;
	size[u]=1;
	for(i=0;i<G[u].size();i++)
	{
		v=G[u][i];
		DFS1(v);
		size[u]+=size[v];
		if(size[son[u]]<size[v])son[u]=v;
	}
}
void DFS2(int u)
{
	if(size[u]==1)
	{
	    P[u]=u;
		return ;
	}
	int i,v;
	for(i=0;i<G[u].size();i++)
	{
		v=G[u][i];
		DFS2(v);
	}
	v=P[son[u]];
	while(!check(u,v))v=fa[v];
	P[u]=v;
}
void read()
{
	cin>>n;
	for(int i=2;i<=n;i++)
	{
		cin>>fa[i];
		G[fa[i]].push_back(i);
	}
}

void work()
{
	DFS1(1);
	DFS2(1);
	for(int i=1;i<=n;i++)cout<<P[i]<<endl;
}
int main()
{
	read();
	work();
	return 0;
}