题意：一个森林，加边，询问路径上k小值。保证任意时刻是森林

---

LCT没法搞，树上kth肯定要用树上主席树

加边？启发式合并就好了，小的树dfs重建一下

注意

1. 测试点编号不是数据组数！！！
2. 加边的时候要更新邻接链表啊，并且fa要清空
3. 并查集维护size一定初始化1

好了现在我要填报名表了

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;typedef long long ll;#define lc(x) t[x].l#define rc(x) t[x].rconst int N=1e5+5, M=2e5+5;inline int read(){    char c=getchar();int x=0,f=1;    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}int n, m, Q, a[N], u, v, k, mp[N]; char s[5];namespace ufs{    int fa[N], size[N];    int find(int x) {return x==fa[x]?x:fa[x]=find(fa[x]);}} using ufs::size; using ufs::find;struct edge{int v,ne;}e[M];int cnt, h[N];inline void ins(int u, int v) {    e[++cnt]=(edge){v, h[u]}; h[u]=cnt;    e[++cnt]=(edge){u, h[v]}; h[v]=cnt;}int vis[N], fa[N][18], deep[N];int lca(int x, int y) {    if(deep[x]
        
         =0; i--)         if(fa[x][i] != fa[y][i]) x=fa[x][i], y=fa[y][i];    return fa[x][0];}struct ChairTree{    struct meow{int l,r,size;}t[N*85];    int sz, root[N];    void insert(int &x, int l, int r, int p) {        t[++sz]=t[x]; x=sz;        t[x].size++;        if(l==r) return;        int mid=(l+r)>>1;        if(p<=mid) insert(lc(x), l, mid, p);        else insert(rc(x), mid+1, r, p);    }    void build(int u) { //printf("build %d %d\n",u,fa[u][0]);        vis[u]=1;        for(int i=1; (1<
         
          <=deep[u]; i++) fa[u][i] = fa[ fa[u][i-1] ][i-1]; root[u] = root[fa[u][0]]; insert(root[u], 1, *mp, a[u]); for(int i=h[u];i;i=e[i].ne) if(e[i].v != fa[u][0]) { fa[e[i].v][0]=u; deep[e[i].v]=deep[u]+1; build(e[i].v); } } int query(int u, int v, int k) { int f=lca(u,v), g=fa[f][0]; int x=root[u], y=root[v], l=1, r=*mp; f=root[f]; g=root[g]; while(l!=r) { int lsize = t[lc(x)].size + t[lc(y)].size - t[lc(f)].size - t[lc(g)].size; int mid=(l+r)>>1; if(k<=lsize) x=lc(x), y=lc(y), f=lc(f), g=lc(g), r=mid; else x=rc(x), y=rc(y), f=rc(f), g=rc(g), l=mid+1, k-=lsize; } return l; } void rebuild(int u) { for(int i=1; i<17; i++) fa[u][i] = fa[ fa[u][i-1] ][i-1]; root[u] = root[fa[u][0]]; insert(root[u], 1, *mp, a[u]); for(int i=h[u];i;i=e[i].ne) if(e[i].v != fa[u][0]) { fa[e[i].v][0]=u; deep[e[i].v]=deep[u]+1; rebuild(e[i].v); } } void Link(int u, int v) { int x=find(u), y=find(v); if(size[x]