题意：

有一棵n个结点的树，结点编号分别为1～n，询问对于每个结点，它的子结点中有多少结点的编号比它小。

思路：

这里用到了dfs序。

dfs序的介绍见这里：https://www.bilibili.com/video/av4482146?from=search&seid=7981889138645681255。

dfs序有一个可以利用的性质是每一棵子树在序列里都是连续的，所以可以对每个结点给两个时间戳，一个是遍历到该点时的时间戳，另一个是从该点出去的时间戳。

比如样例如图，

可以得到一个dfs序为7 10 14 2 13 1 9 11 6 5 8 3 15 12 4，

1～15的时间戳分别为(6,6)(4,4)(12,14)(15,15)(10,10)(9,11)(1,15)(11,11)(7,11)(2,5)(8,8)(14,14)(5,5)(3,5)(13,13)。

时间戳区间内的结点都为该结点的子结点。

因为要求的是子树中编号比它小的结点数，所以从1～n遍历，类似于逆序数的做法，查询时间戳区间内的区间和得到的就是子树中编号比它小的结点个数，之后再将入时间戳的位置置为1。

vector不清空也会OLE啊…

代码：

vector<int>v[100010];
bool vis[100010];
int cnt;
int intime[100010];//入时间戳
int outime[100010];//出时间戳
int ans[100010];
int d[100010];
void dfs(int id)
{
    vis[id]=true;
    intime[id]=++cnt;
    for(int i=0;i<v[id].size();i++)
    {
        if(!vis[v[id][i]])
            dfs(v[id][i]);
    }
    outime[id]=cnt;
}
int lowbit(int x)
{
    return x&(-x);
}
int query(int x)
{
    int res=0;
    while(x)
    {
        res+=d[x];
        x-=lowbit(x);
    }
    return res;
}
void add(int x,int v)
{
    while(x<=cnt)
    {
        d[x]+=v;
        x+=lowbit(x);
    }
}
int main()
{
    int n,p,x,y;
    while(scanf("%d%d",&n,&p)!=EOF)
    {
        if(n==0&&p==0)break;
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++)
            v[i].clear();
        for(int i=0;i<n-1;i++)
        {
            scanf("%d%d",&x,&y);
            v[x].push_back(y);
            v[y].push_back(x);
        }
        cnt=0;
        dfs(p);
        memset(d,0,sizeof(d));
        for(int i=1;i<=n;i++)
        {
            ans[i]=query(outime[i])-query(intime[i]-1);
            add(intime[i],1);
        }
        for(int i=1;i<=n;i++)
            printf("(%d,%d)",intime[i],outime[i]);
        for(int i=1;i<n;i++)
            printf("%d ",ans[i]);
        printf("%d\n",ans[n]);
    }
    return 0;
}