第k小，很容易会想到用主席树来解决
这里简单想一下树的转移过程
因为本身无向图形成一棵树，那么我们总以1为根，那么之后连下去的边对应的点建立的线段树总是在父亲节点对应的树上加上一个当前点对应位置出现的值
这跟在普通序列上由前一个转移到下一个是差不多的
那么每个点上生成的线段树记录的就是当前节点到根节点的总信息
然后每次询问求出2个点的公共祖先，那么找第k小，总是两个点的总前缀 减去一个 公共祖先的前缀和公共祖先父亲的前缀
那么询问的时候只要查询这四个点对应的线段树的值就可以了
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 #define N 100010 5 #define lowbit(x) x&(-x) 6 #define define_m int m=(l+r)>>1 7 #define LS(x) node[x].ls 8 #define RS(x) node[x].rs 9 #define INIT(x) node[x].init() 10 #define SZ(x) node[x].sz 11 12 int a[N] , val[N] , fa[N] , T[N]; 13 int n , m , first[N] , k , curn;//curn表示离散化后还剩多少种数 14 15 //LCA所需 16 int dp[N<<1][30]; 17 int id[N<<1] , dep[N<<1] , No[N] , dfs_clock; 18 19 int HASH(int x){return lower_bound(a+1 , a+curn+1 , x)-a;} 20 21 struct Node{ 22 int ls , rs , sz; 23 void init(){ls=rs=sz=0;} 24 }node[N*40]; 25 26 int tot; 27 int build(int l , int r) 28 { 29 int u=tot++; 30 INIT(u); 31 if(l!=r){ 32 define_m; 33 LS(u) = build(l , m); 34 RS(u) = build(m+1 , r); 35 } 36 return u; 37 } 38 39 void build(int o1 , int o2 , int l , int r , int pos , int v) 40 { 41 if(l==r){ 42 SZ(o2) = SZ(o1)+v; 43 return; 44 } 45 define_m; 46 INIT(tot); 47 if(m>=pos){ 48 LS(o2) = tot++ , RS(o2) = RS(o1); 49 build(LS(o1) , LS(o2) , l , m , pos , v); 50 }else{ 51 LS(o2) = LS(o1) , RS(o2) = tot++; 52 build(RS(o1) , RS(o2) , m+1 , r , pos , v); 53 } 54 SZ(o2) = SZ(LS(o2)) + SZ(RS(o2)); 55 } 56 57 int query(int u , int v , int anc1 , int anc2 , int l , int r , int k) 58 { 59 if(l==r) return l; 60 define_m; 61 int c = SZ(LS(u))+SZ(LS(v))-SZ(LS(anc1))-SZ(LS(anc2)); 62 if(c>=k) return query(LS(u) , LS(v) , LS(anc1) , LS(anc2) , l , m , k); 63 else return query(RS(u) , RS(v) , RS(anc1) , RS(anc2) , m+1 , r , k-c); 64 } 65 66 struct Edge{ 67 int x , y , next; 68 Edge(){} 69 Edge(int x , int y , int next):x(x),y(y),next(next){} 70 }e[N<<1]; 71 72 void add_edge(int x , int y){ 73 e[k] = Edge(x , y , first[x]); 74 first[x] = k++; 75 } 76 77 void dfs(int u , int f , int d) 78 { 79 fa[u] = f , id[++dfs_clock] = u , No[u] = dfs_clock , dep[dfs_clock] = d; 80 INIT(tot); 81 T[u] = tot++; 82 build(T[f] , T[u] , 1 , curn , HASH(val[u]) , 1); 83 for(int i=first[u] ; ~i ; i=e[i].next){ 84 int v = e[i].y; 85 if(v == f) continue; 86 dfs(v , u ,d+1); 87 id[++dfs_clock] = u , dep[dfs_clock] = d; 88 } 89 } 90 91 void ST(int n){ 92 for(int i=1 ; i<=n ; i++) dp[i][0] = i; 93 for(int j=1 ; (1<<j)<=n ; j++){ 94 for(int i=1 ; i+(1<<j)-1<=n ; i++){ 95 int a = dp[i][j-1] , b=dp[i+(1<<(j-1))][j-1]; 96 dp[i][j] = dep[a]<dep[b]?a:b; 97 } 98 } 99 } 100 101 int RMQ(int l , int r){ 102 int k=0 ; 103 while((1<<(k+1))<=r-l+1) k++; 104 int a = dp[l][k] , b=dp[r-(1<<k)+1][k]; 105 return dep[a]<dep[b]?a:b; 106 } 107 108 int LCA(int u , int v) 109 { 110 int x = No[u] , y = No[v]; 111 if(x>y) swap(x , y); 112 return id[RMQ(x,y)]; 113 } 114 115 int main() 116 { 117 // freopen("in.txt" , "r" , stdin); 118 //freopen("out1.txt" , "w" , stdout); 119 while(~scanf("%d%d" , &n , &m)){ 120 k =0 ; 121 memset(first , -1 , sizeof(first)); 122 for(int i=1 ; i<=n ; i++){scanf("%d" , &val[i]);a[i]=val[i];} 123 sort(a+1 , a+n+1); 124 curn = unique(a+1 , a+n+1)-(a+1); 125 // cout<<"check: "<<curn<<endl; 126 for(int i=1 ; i<n ; i++){ 127 int x , y; 128 scanf("%d%d" , &x , &y); 129 add_edge(x , y); 130 add_edge(y , x); 131 } 132 dfs_clock = 0; 133 tot=0; 134 INIT(tot); 135 T[0] = build(1 , curn); 136 dfs(1,0,1); 137 ST(2*n-1); 138 while(m--){ 139 int x , y , k; 140 scanf("%d%d%d" , &x , &y , &k); 141 int anc = LCA(x , y); 142 int index = query(T[x] , T[y] , T[anc] , T[fa[anc]] , 1 , curn , k); 143 printf("%d " , a[index]); 144 } 145 } 146 return 0; 147 }