记录编号	201350	评测结果	AAAAAAAAAA
题目名称	[河南省队2012] 座位问题	最终得分	100
用户昵称	forever	是否通过	通过
代码语言	C++	运行时间	0.234 s
提交时间	2015-10-30 17:17:14	内存使用	7.78 MiB

#include<cstdio>
using namespace std;
#define maxn 100010
struct dd{
	int begin,end,next;
}jie[maxn*3];
int Ans[maxn],dfn[maxn],low[maxn],c[maxn],p[maxn];
int n,times,head[maxn],tot;
bool vis[maxn];
inline int in(){
	int TEMP,EPX;
	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 add(int x,int y){
	jie[++tot].end=y; jie[tot].next=head[x]; head[x]=tot;
}
int lowbit(int x){
	return x&(-x);
}
void dfs(int x){
	dfn[x]=++times;vis[x]=1;
	for(int i=head[x];i;i=jie[i].next){
		if(!vis[jie[i].end]) dfs(jie[i].end);
	}
	low[x]=times;
}
void update(int x,int y){
	for(int i=x;i<=times;i+=lowbit(i)) c[i]+=y;
	return;
}
inline int Que(int x){
	int sum=0;
	for(int i=x;i>0;i-=lowbit(i)) sum+=c[i];
	return sum;
}
int main(){
    freopen("seat.in","r",stdin);
    freopen("seat.out","w",stdout);
    n=in();
	for(int i=1;i<n;++i){
		int x,y;
		x=in();y=in();
        add(x,y);add(y,x);
	}
	for(int i=1;i<=n;++i) p[i]=in();
	dfs(1);
	for(int i=1;i<=n;++i){
		Ans[i]=Que(dfn[p[i]]);
		update(dfn[p[i]]+1,1); update(low[p[i]]+1,-1);
	}
	for(int i=1;i<=n;++i) printf("%d\n",Ans[i]);
	getchar();getchar();
	return 0;
}