戳这里看题面

一道挺有意思的题，可以练一下板子

大意：给出$n(1\le n \le10^5)$个结点的树，$m$组询问，求 以$x$为根节点的树中 第$k$小的数（从小到大第$k$个）

题目中没翻译清楚，该树树以$1$为根节点

思路：

对于树上操作，我已开始想到的是树剖，但是题目中所求的是以$x$为根的树，那么那么就应该想到DFS序

这和树剖一样，是一个能将树形结构转化为线性结构的神奇的东西

确定了使用$DFS$序之后，对于树中第$k$小，由于它是不带修的，所以很容易想到使用主席树

然后就开始乱搞了

注意要点：

题目中所求的是第$k$小点的编号！！

主席树查询出结果后，这个l值不是实际上的编号

因为主席树最后得到l==r的时候，l的值实际上是这个点在权值线段树中的位置

而这个点原先的Id并不一定是l，所以还要记录一下Id然后再对应回去

具体详见代码吧，结合代码说的更清楚

Code：

#include<bits/stdc++.h>
#define N 100010
using namespace std;
struct node{
    int to,nxt;
}b[N<<1];
struct Node{
    int l,r,sum;
}T[N*80];//开大点没事，但是算一下，实际上40差不多了
int head[N],in[N],out[N],a[N],p[N],rev[N],root[N],Id[N];
int n,Ts,num,x,y,res,t,ans,k;//rev数组将dfs序对应会原来的编号
int read()
{
    int s=0;
    char c=getchar();
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c))
    {
        s=(s<<1)+(s<<3)+c-'0';
        c=getchar();
    }
    return s;
}
void add(int x,int y){
    b[++t].to=y;b[t].nxt=head[x];head[x]=t;
    b[++t].to=x;b[t].nxt=head[y];head[y]=t;
}
void dfs(int k,int fa)//这里求的是dfs序，in[k]表示k这个点的dfs序
{//out[k]表示k这个点的子树中最大dfs序，也就是说，在in[k]~out[k]这个区间，都是以k为根的树 的节点的dfs序
    in[k]=++num;//有点绕口
    rev[num]=k;
    int i,to;
    for(i=head[k];i;i=b[i].nxt)
    {
        to=b[i].to;
        if(to==fa)
            continue;
        dfs(to,k);
    }
    out[k]=num;
}
void Modify(int l,int r,int &x,int y,int pos,int i)
{
    T[++res]=T[y];T[res].sum++;x=res;
    if(l==r)
    {
        Id[l]=i;//顺便记录一下这个点原先的编号
        return;
    }
    int mid=(l+r)>>1;
    if(pos<=mid)
        Modify(l,mid,T[x].l,T[y].l,pos,i);
    else
        Modify(mid+1,r,T[x].r,T[y].r,pos,i);
}
void query(int l,int r,int x,int y,int k)
{
    if(l==r)
    {
        ans=Id[l];//这样就可以直接对应了
        return;
    }
    int mid=(l+r)>>1;
    int sum=T[T[y].l].sum-T[T[x].l].sum;
    if(k<=sum)
        query(l,mid,T[x].l,T[y].l,k);
    else
        query(mid+1,r,T[x].r,T[y].r,k-sum);
}
int main()
{
    int i;
    n=read();
    for(i=1;i<=n;i++)
        p[i]=a[i]=read();
    for(i=1;i<n;i++)
    {
        x=read();y=read();
        add(x,y);
    }
    dfs(1,0);
    sort(p+1,p+1+n);
    for(i=1;i<=n;i++)//i表示的是dfs序
    {
        a[rev[i]]=lower_bound(p+1,p+1+n,a[rev[i]])-p;//离散化
        Modify(1,n,root[i],root[i-1],a[rev[i]],rev[i]);
    }
    Ts=read();
    while(Ts--)
    {
        x=read();k=read();
        query(1,n,root[in[x]-1],root[out[x]],k);
        printf("%d\n",ans);
    }
    return 0;
}

devil.