| 比赛 | 
    20120718 | 
    评测结果 | 
    AAAAAAAATT | 
    | 题目名称 | 
    座位问题 | 
    最终得分 | 
    80 | 
    | 用户昵称 | 
    Citron酱 | 
    运行时间 | 
    0.307 s  | 
    | 代码语言 | 
    C++ | 
    内存使用 | 
    3.43 MiB  | 
    | 提交时间 | 
    2012-07-18 08:16:32 | 
显示代码纯文本
#include <cstdio>
#define I_F "seat.in"
#define O_F "seat.out"
const long MAXn=100000;
const long MAXm=MAXn*2;
struct edge
{
	long x;
	edge *next;
};
edge pool[MAXm];
edge *ph=pool;
edge *map[MAXn]={NULL};
long n;
long g[MAXn];
long d[MAXn]={-1};
bool f[MAXn]={false};
long ans[MAXn]={0};
void Input();
void Dfs(const long&);
void Search();
void Output();
int main()
{
	Input();
	Dfs(0);
	Search();
	Output();
	return 0;
}
void Input()
{
	edge *temp;
	long a, b;
	freopen(I_F,"r",stdin);
	scanf("%ld",&n);
	for (long i=1; i<n; ++i)
	{
		scanf("%ld%ld",&a,&b);
		--a, --b;
		temp=map[a];
		map[a]=ph++;
		map[a]->x=b;
		map[a]->next=temp;
		temp=map[b];
		map[b]=ph++;
		map[b]->x=a;
		map[b]->next=temp;
	}
	for (long i=0; i<n; ++i)
	{
		scanf("%ld",&g[i]);
		--g[i];
	}
}
void Dfs(const long &x)
{
	f[x]=true;
	for (edge *i=map[x]; i!=NULL; i=i->next)
		if (f[i->x])
			d[x]=i->x;
		else
			Dfs(i->x);
}
void Search()
{
	for (long i=0; i<n; ++i)
		f[i]=false;
	for (long i=0; i<n; ++i)
	{
		f[g[i]]=true;
		for (long j=d[g[i]]; j!=-1; j=d[j])
			if (f[j])
				++ans[i];
	}
}
void Output()
{
	freopen(O_F,"w",stdout);
	for (long i=0; i<n; ++i)
		printf("%ld\n",ans[i]);
}