Sgu/195

#include<cstdio>
#include<algorithm>
using namespace std;
 
const int MAX=500000+10;
const int INF=10000000;
int n;
int fa[MAX];
int t[MAX],begin[MAX],next[MAX],tot;
int f[MAX][2];//0 选根节点   1 不选根节点
int choose[MAX];
int answer[MAX];
 
void addedge(int x,int y)
{
	t[++tot]=y;
	next[tot]=begin[x];begin[x]=tot;
}
 
void dfs(int u)
{
	int v,i=0,ans=0,max=-INF;
	f[u][0]=1;
	for(i=begin[u];i;i=next[i])
	{
		v=t[i];
		dfs(v);
		ans+=f[v][1];
		if(f[v][0]-f[v][1]>max){max=f[v][0]-f[v][1];choose[u]=v;}
	}
	f[u][0]+=ans;
	if(ans+max>f[u][1])f[u][1]=ans+max;
}
 
void get(int u,int i)
{
	int v,j;
	if(i==0)answer[++answer[0]]=u;
	for(j=begin[u];j;j=next[j])
	{
		v=t[j];
		if(i==0)
			get(v,1);
		else 
			get(v,choose[u]!=v);
	}
}
 
int main()
{
	#ifndef ONLINE_JUDGE
	freopen("195.in","r",stdin);freopen("195.out","w",stdout);
	#endif
	int i;
	scanf("%d",&n);
	for(i=2;i<=n;++i)
	{
		scanf("%d",&fa[i]);
		addedge(fa[i],i);
	}
	dfs(1);
	printf("%d\n",f[1][1]*1000);
	get(1,1);
	sort(answer+1,answer+answer[0]+1);
	for(i=1;i<=answer[0];++i)
		printf("%d ",answer[i]);
	printf("\n");
	return 0;
}

/by Logic
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn=500050;
int n,fa[maxn],f[maxn][2]={0};
int now,a[maxn*2]={0},ne[maxn*2]={0};
bool get[maxn*2]={0};
int anss=0,ans[maxn];
void ins(int x,int y)
{
	if(!a[x]) a[x]=y;
	else now++,a[now]=y,ne[now]=ne[x],ne[x]=now;
}
void dfs(int cur)
{
	int i,ch=0;
	for(i=cur;a[i];i=ne[i])
	{
		dfs(a[i]);
		f[cur][0]+=f[a[i]][0];
		if(f[a[i]][1]-f[a[i]][0]>f[ch][1]-f[ch][0])
			ch=a[i];
		f[cur][1]+=f[a[i]][0];
	}
	if(ch)
		f[cur][0]+=f[ch][1]-f[ch][0],get[ch]=1;
	f[cur][1]++;
}
void dfs2(int cur,int whe)
{
	int i;
	if(whe) ans[anss++]=cur;
	for(i=cur;a[i];i=ne[i])
		dfs2(a[i],!whe&&get[a[i]]);
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("data.in","r",stdin);
#endif
	int i;
	scanf("%d",&n);
	now=n;
	for(i=2;i<=n;i++)
		scanf("%d",&fa[i]),ins(fa[i],i);
	dfs(1);
	printf("%d\n",f[1][0]*1000);
	dfs2(1,0);
	sort(ans,ans+anss);
	for(i=0;i<anss;i++)
		printf("%d ",ans[i]);
	return 0;
}