记录编号	40569	评测结果	EEEEEEEEEE
题目名称	[河南省队2012] 找第k小的数	最终得分	0
用户昵称	TBK	是否通过	未通过
代码语言	C++	运行时间	0.697 s
提交时间	2012-07-18 13:50:34	内存使用	6.89 MiB

#include <iostream>
#include <cmath>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <set>
#include <algorithm>
#define MAXN 0x7fffffff
using namespace std;
int a[100001],b,c,d,r[100002],p[1000000],q,tail=0,k[100001],l=1,t,s;
struct fun
{
    int x,y;
}f[200000];
bool bo[100001];
int Compare( const void *a , const void *b )
{
    struct fun *c = (struct fun *)a;
    struct fun *d = (struct fun *)b;
    if (c->x != d->x) return c->x - d->x;
        else return c->y - d->y;
}
int main(void)
{   
    freopen("seat.in","r",stdin);
    freopen("seat.out","w",stdout);
    scanf("%d",&b);
    for (c=0;c<b-1;c++) 
    {
        scanf("%d%d",&f[c].x,&f[c].y);
        f[c+b-1].x=f[c].y;
        f[c+b-1].y=f[c].x;
    }
    for (c=1;c<=b;c++) scanf("%d",&a[c]);
    qsort(f,2*b-2,sizeof(fun),Compare);
    for (c=1;c<2*b-2;c++)
        if (f[c].x!=f[c-1].x)
        {
            r[l]=c;
            l++;
        }
	r[b]=2*b-2;
    p[q]=1;
    q++;
    tail=0;
    k[1]=-1;
    while (tail<=q)
    {
        for (c=r[p[tail]-1];c<r[p[tail]];c++)
            if (k[f[c].y]==0) 
            {
                k[f[c].y]=p[tail];
                p[q]=f[c].y;
                q++;
            }
        tail++;
    }
    for (c=1;c<=b;c++)
    {
        t=a[c];
        bo[t]=true;
        s=0;
        while (t!=-1)
        {
            t=k[t];
            if (bo[t]==true) s++;
        }
        printf("%d\n",s);
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}