记录编号 201342 评测结果 AAAAAAAAAA
题目名称 [河南省队2012] 座位问题 最终得分 100
用户昵称 Gravatar真红之蝶 是否通过 通过
代码语言 C++ 运行时间 0.251 s
提交时间 2015-10-30 17:04:08 内存使用 3.73 MiB
显示代码纯文本
#include<stdio.h>
#define push(a) stack[++top]=a
#define solve(a,top) for(int i=a;i<=top;++i){ int u=stack[i];if(w[u]<w[x])ans[w[x]]++;}
#define pop top--;
int n,a,b,first[100005],tot,ans[100005],stack[100005],top,v[100005],w[100005],x;
struct data
{
	int v,next;
}s[200005];
int TEMP,EPX;
inline int in()
{
	TEMP=0;EPX=getchar();
	while(EPX<48||EPX>57)
		EPX=getchar();
	for(;EPX>47&&EPX<58;EPX=getchar())
		TEMP=(TEMP<<3)+(TEMP<<1)+EPX-48;
	return TEMP;
}
void dfs(int x)
{
	solve(1,top);
	v[x]=1;push(x);
	for(int i=first[x];i;i=s[i].next)
	{
		int j=s[i].v;
		if(!v[j])dfs(j);
	}pop;
}
int main()
{
	freopen("seat.in","r",stdin);
	freopen("seat.out","w",stdout);
   	n=in();
	for(int i=1;i<n;++i)
	{
		a=in(),b=in();
        s[++tot].v=b;s[tot].next=first[a];first[a]=tot;
        s[++tot].v=a;s[tot].next=first[b];first[b]=tot;
	}
	n++;
	for(int i=1;i<n;++i)
	{
		x=in();
		w[x]=i;
	}
	dfs(1);
	for(int i=1;i<n;++i)
		printf("%d\n",ans[i]);
}
/*5 1 4 5 4 1 3 2 4 4 2 1 5 3*/