记录编号	366113	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[SCOI 2008] 斜堆	最终得分	100
用户昵称	小一米	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2017-01-22 18:26:03	内存使用	0.31 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n,root;
int fa[55],son[55][2],ans[55],siz[55];
int cal(int x)
{
	if (son[x][0]==-1) return x;
	if (son[x][1]==-1&&siz[son[x][0]]>1) return x;
	if (son[x][1]!=-1) return cal(son[x][0]);
	else return max(x,cal(son[x][0]));
}
void del(int x)
{
	int t=fa[x];
	if (t!=-1) son[t][0]=son[x][0];
	if (son[x][0]!=-1) fa[son[x][0]]=t;
	if (fa[x]==-1) root=son[x][0];
	for (;t!=-1;t=fa[t])
	{
		--siz[t];
		swap(son[t][0],son[t][1]);
	}
}
main()
{
	freopen("heap.in","r",stdin);
	freopen("heap.out","w",stdout);
	scanf("%d",&n);
	memset(fa,-1,sizeof(fa));
	memset(son,-1,sizeof(son));
	for (int x,i=1;i<=n;++i)
	{
		scanf("%d",&x);
		if (x<100) son[x][0]=i,fa[i]=x;
		else son[x-100][1]=i,fa[i]=x-100;
	}
	siz[0]=1;
	for (int i=n;i>=1;--i) ++siz[i],siz[fa[i]]+=siz[i];
	root=0;
	for (int i=n;i>=0;--i)
		ans[i]=cal(root),
		del(ans[i]);
	for (int i=0;i<=n;++i) printf("%d ",ans[i]);
}