比赛 20120718 评测结果 AAAAAAAATT
题目名称 座位问题 最终得分 80
用户昵称 Czb。 运行时间 0.304 s
代码语言 C++ 内存使用 1.93 MiB
提交时间 2012-07-18 09:03:09
显示代码纯文本
#include<stdio.h>
#include<vector>
#include<queue>

using namespace std;

int n,last[100001];

bool flag[100001];

vector <int> v[100001];

queue <int> Q;

int main()
{
	freopen("seat.in","r",stdin);
	freopen("seat.out","w",stdout);
	int i,x,y;
	scanf("%d",&n);
	for(i=1;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		v[x].push_back(y);
		v[y].push_back(x);
	}
	Q.push(1);
	last[1]=0;
	flag[1]=true;
	while(!Q.empty())
	{
		x=Q.front();
		for(i=0;i<v[x].size();i++)
		{
			if(!flag[v[x][i]])
			{
				Q.push(v[x][i]);
				last[v[x][i]]=x;
				flag[v[x][i]]=true;
			}
		}
		Q.pop();
	}
	for(i=1;i<=n;i++)
	{
		scanf("%d",&x);
		int ans=0;
		flag[x]=false;
		for(x=last[x];x;x=last[x])
		{
			if(!flag[x])
				ans++;
		}
		printf("%d\n",ans);
	}
	return 0;
}