树上第k小，可持久化线段树+倍增lca

给定一颗树，树的每个结点都有权值，

有q个询问，每个询问是 u v k ,表示u到v路径上第k小的权值是多少。

每个结点所表示的线段树，是父亲结点的线段树添加该结点的权值之后形成的新的线段树

c[root] 表示根为root的子树添加了多少个结点。

那么c[lson[u]] + c[lson[v]] - c[lson[lca(u,v)]] - c[lson[fa[lca(u,v)]]]  >=k ,那么说明左子树添加了k个以上的结点，说明第k小的值在左子树

否则就在右子树。

 //

 //  main.cpp

 //  函数式线段树

 //

 //  Created by whoami on 15/9/21.

 //  Copyright (c) 2015年 whoami. All rights reserved.

 //

 #include <iostream>

 #include <algorithm>

 #include <stdio.h>

 #include <string.h>

 using namespace std;

 const int N =  + ;

 const int M = ;

 int t[N],lson[N],rson[N],c[N],total;

 int a[M],b[M];

 int n,m,q;

 int head[M],nxt[M],to[M],e;

 int dfs_clock,iid[M];

 int fa[M][],depth[M];

 void addEdge(int u, int v){

     to[e] = v;

     nxt[e] = head[u];

     head[u] = e++;

 }

 //离散化，离散化后有多少个点，线段树的区间就是多大

 void initHash(){

     sort(b+,b+n+);

     m = unique(b+,b+n+) - b - ;

 }

 int hs(int x){

     return lower_bound(b+,b+m+,x)-b;

 }

 int build(int l, int r){

     int root = total++;

     c[root] = ;

     if(l!=r){

         int mid = (l+r)>>;

         lson[root] = build(l,mid);

         rson[root] = build(mid+,r);

     }

     return root;

 }

 int update(int root, int pos, int val){

     int newRoot = total++,tmp = newRoot;

     c[newRoot] = c[root] + val;

     int l =, r = m;

     while(l<r){

         int mid = (l+r)>>;

         if(pos<=mid){

             r = mid;

             lson[newRoot] = total++;

             rson[newRoot] = rson[root];

             newRoot = lson[newRoot];

             root = lson[root];

         }

         else{

             l = mid + ;

             lson[newRoot] = lson[root];

             rson[newRoot] = total++;

             newRoot = rson[newRoot];

             root = rson[root];

         }

         c[newRoot] = c[root] + val;

     }

     return tmp;

 }

 void dfs(int u, int f, int dep){

     fa[u][] = f;

     depth[u] = dep;

     for(int i=head[u]; i+;i=nxt[i]){

         int v = to[i];

         if(v==f)continue;

         t[++dfs_clock] = update(iid[u],hs(a[v]),);

         iid[v] = t[dfs_clock];

         dfs(v,u,dep+);

     }

 }

 int query(int urt, int vrt, int lcart, int frt, int k){

     int l = , r = m;

     //当l==r,即区间的长度只有1时，那么该区间所对应的值就是第k小了

     while(l<r){

         int mid = (l+r)>>;

         if(c[lson[urt]] + c[lson[vrt]] - c[lson[frt]]-c[lson[lcart]]>=k){

             r = mid;

             urt = lson[urt];

             vrt = lson[vrt];

             frt = lson[frt];

             lcart = lson[lcart];

         }

         else

         {

             l = mid+;

             k -= c[lson[urt]] + c[lson[vrt]] - c[lson[frt]]-c[lson[lcart]];

             urt = rson[urt];

             vrt = rson[vrt];

             frt = rson[frt];

             lcart = rson[lcart];

         }

     }

     return l;

 }

 void init() {

     for(int k=;k+<; ++k){

         for(int v = ;v<=n;++v){

             if(fa[v][k]<)

                 fa[v][k+] = -;

             else

                 fa[v][k+] = fa[fa[v][k]][k];

         }

     }

 }

 int lca(int u, int  v){

     if(depth[u] < depth[v])

         swap(u,v);

     int tmp = depth[u] - depth[v];

     for(int i=;i>=;--i)

         if(tmp &(<<i))

         u = fa[u][i];

     if(u==v) return u;

     for(int i=;i>=;--i){

         if(fa[u][i]!=fa[v][i]){

             u = fa[u][i];

             v = fa[v][i];

         }

     }

     return fa[u][];

 }

 int main(int argc, const char * argv[]) {

     int u,v,k;

     while(scanf("%d%d",&n,&q)!=EOF){

         total = dfs_clock = ;

         for(int i=;i<=n;++i){

             scanf("%d",&a[i]);

             b[i] = a[i];

         }

         memset(head,-,sizeof(head));

         for(int i=;i<n;++i){

             scanf("%d%d",&u,&v);

             addEdge(u,v);

             addEdge(v,u);

         }

         addEdge(,);

         addEdge(,);

         initHash();

         iid[] = t[] = build(,m);

         memset(fa,-,sizeof(fa));

         dfs(,,);

         init();

         while(q--){

             scanf("%d%d%d",&u,&v,&k);

             int lc = lca(u,v);

             int f = fa[lc][];

             printf("%d\n",b[query(iid[u],iid[v],iid[lc],iid[f],k)]);

         }

     }

     return ;

 }