记录编号	40606	评测结果	AAAAAAAAAT
题目名称	936.[河南省队2012] 座位问题	最终得分	90
用户昵称	Truth.Cirno	是否通过	未通过
代码语言	C++	运行时间	0.296 s
提交时间	2012-07-18 14:51:40	内存使用	2.77 MiB

#include <cstdio>
using namespace std;

int ava=1,way[200001],nextway[200001],ptow[100001],dad[100001];
bool right[100001]={0},used[100001];

void addway(int x,int y)
{
	int pos;
	pos=ptow[x];
	if (pos==0)
	{
		ptow[x]=ava;
		way[ava++]=y;
	}
	else
	{
		while (nextway[pos])
			pos=nextway[pos];
		nextway[pos]=ava;
		way[ava++]=y;
	}
}

void filldad(int from,int pos)
{
	dad[pos]=from;
	used[pos]=true;
	int poi;
	poi=ptow[pos];
	while (poi)
	{
		if (!used[way[poi]])
			filldad(pos,way[poi]);
		poi=nextway[poi];
	}
	used[pos]=false;
}

int main(void)
{
	freopen("seat.in","r",stdin);
	freopen("seat.out","w",stdout);
	int i,n,x,y,c,temp;
	scanf("%d",&n);
	for (i=1;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		addway(x,y);
		addway(y,x);
	}
	filldad(0,1);
	for (i=1;i<=n;i++)
	{
		scanf("%d",&x);
		c=0;
		temp=x;
		while (x)
		{
			c+=right[x];
			x=dad[x];
		}
		printf("%d\n",c);
		right[temp]=1;
	}
	return(0);
}