大致题意： 给你一棵树，每次问你两点之间第\(k\)小的点权，强制在线。

主席树

这种题目强制在线一般就是数据结构了。

而看到区间第\(k\)小，很容易就能想到。

至少不会有人想到树套树。

树上主席树

与一般的主席树不同，这题的主席树是树上主席树（不过许多奆佬称其为主席树上树）。

维护数列的主席树，我们一般是由前一个数的主席树构造当前树的主席树。

而树上的主席树其实也是类似的，可以由父亲节点的主席树构造当前树的主席树。

关于查询操作

关于查询两个节点\(x,y\)路径间第\(k\)小的权值，我们进行如下操作：

• 首先，找到\(x\)和\(y\)的\(LCA\)，姑且命名它为\(z\)。
• 然后，我们可以进行差分，即用\(x\)和\(y\)的值与\(z\)和\(fa_z\)的值相减，就可以得出最终的答案（这与数组版的主席树是类似的）。

对于\(LCA\)，我们可以直接用。

然后我们就可以发现这是一道主席树板子题。

代码

#include
    
     #define max(x,y) ((x)>(y)?(x):(y))#define min(x,y) ((x)<(y)?(x):(y))#define uint unsigned int#define LL long long#define ull unsigned long long#define swap(x,y) (x^=y,y^=x,x^=y)#define abs(x) ((x)<0?-(x):(x))#define INF 1e9#define Inc(x,y) ((x+=(y))>=MOD&&(x-=MOD))#define ten(x) (((x)<<3)+((x)<<1))#define N 100000#define LogN 20#define add(x,y) (e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y)using namespace std;int n,cnt,ee=0,a[N+5],p[N+5],lnk[N+5],Depth[N+5],fa[N+5][LogN+5];struct edge{    int to,nxt;}e[(N<<1)+5];class FIO{    private:        #define Fsize 100000        #define tc() (FinNow==FinEnd&&(FinEnd=(FinNow=Fin)+fread(Fin,1,Fsize,stdin),FinNow==FinEnd)?EOF:*FinNow++)        #define pc(ch) (FoutSize
     
      =0;--i) if(fa[x][i]^fa[y][i]) x=fa[x][i],y=fa[y][i];    return fa[x][0];}class Class_ChairmanTree//主席树{    private:        int n,tot,Root[N+5];        struct Tree        {            int Val,Size,Son[2];        }node[N*LogN+5];        inline void Build(int l,int r,int &rt)//建树        {            if(!rt&&(rt=++tot),!(l^r)) return;            register int mid=l+r>>1;            Build(l,mid,node[rt].Son[0]),Build(mid+1,r,node[rt].Son[1]);        }        inline void ins(int l,int r,int &rt,int lst,int val)//插入        {            if(node[rt=++tot]=node[lst],++node[rt].Size,!(l^r)) return;            register int mid=l+r>>1;            val<=mid?ins(l,mid,node[rt].Son[0],node[lst].Son[0],val):ins(mid+1,r,node[rt].Son[1],node[lst].Son[1],val);        }        inline int qry(int l,int r,int rt1,int rt2,int rt3,int rt4,int k)//查询        {            if(!(l^r)) return l;            register int mid=l+r>>1,t=node[node[rt3].Son[0]].Size+node[node[rt4].Son[0]].Size-node[node[rt1].Son[0]].Size-node[node[rt2].Son[0]].Size;            if(t>=k) return qry(l,mid,node[rt1].Son[0],node[rt2].Son[0],node[rt3].Son[0],node[rt4].Son[0],k);            else return qry(mid+1,r,node[rt1].Son[1],node[rt2].Son[1],node[rt3].Son[1],node[rt4].Son[1],k-t);        }    public:        inline void Init(int len) {Build(1,n=len,Root[0]);}//初始化        inline void Insert(int v,int nv,int val) {ins(1,n,Root[nv],Root[v],val);}        inline int Query(int v1,int v2,int k) {return qry(1,n,Root[LCA(v1,v2)],Root[fa[LCA(v1,v2)][0]],Root[v1],Root[v2],k);}}ChairmanTree;inline int find(int x)//离散化{    register int l=1,r=cnt,mid=l+r>>1;    for(;l<=r;mid=l+r>>1) p[mid]