记录编号 |
201342 |
评测结果 |
AAAAAAAAAA |
题目名称 |
[河南省队2012] 座位问题 |
最终得分 |
100 |
用户昵称 |
真红之蝶 |
是否通过 |
通过 |
代码语言 |
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*/