比赛 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]);
}