比赛 20120718 评测结果 AAAAAAAATT
题目名称 座位问题 最终得分 80
用户昵称 kaaala 运行时间 0.325 s
代码语言 C++ 内存使用 1.17 MiB
提交时间 2012-07-18 10:09:30
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<deque>

using namespace std;

struct edge
{
	int t;
	edge *next;
	edge(int _t,edge *_next):t(_t),next(_next){}
}*Map[100010];

int N,ans,pre[100010];
bool flag[100010];
deque<int>deq;

void addedge(int s,int t)
{
	Map[s]=new edge(t,Map[s]);
	Map[t]=new edge(s,Map[t]);
}

int main()
{
	freopen("seat.in","r",stdin);
	freopen("seat.out","w",stdout);
	scanf("%d",&N);
	for(int i=1;i<N;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		addedge(a,b);
	}
	deq.push_back(1);
	pre[1]=0;
	flag[1]=true;
	while(!deq.empty())
	{
		int u=deq.front();
		deq.pop_front();
		for(edge *p=Map[u];p;p=p->next)
		{
			int t=p->t;
			if(!flag[t])
			{
				deq.push_back(t);
				pre[t]=u;
				flag[t]=true;
			}
		}
	}
	for(int i=1;i<=N;i++)
	{
		int x;
		scanf("%d",&x);
		flag[x]=false;
		ans=0;
		for(x=pre[x];x;x=pre[x])
			if(!flag[x])
				ans++;
		printf("%d\n",ans);
	}
	return 0;
}