data-structure - Persistent Segment Tree ( COT )

#include <bits/stdc++.h>
using namespace std;
/*------- Constants---- */

#define Long                    long long
#define Ulong                   unsigned long long
#define forn(i,n)               for( int i=0 ; i < n ; i++ )
#define mp(i,j)                 make_pair(i,j)
#define pb(a)                   push_back((a))
#define all(x)                  (x).begin(),(x).end()
#define gc                      getchar_unlocked
#define PI                      acos(-1.0)
#define EPS                     1e-9
#define xx                      first
#define yy                      second
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define Di(x)                   int x;scanf("%d",&x)
#define min(a,b)                ((a)>(b) ? (b) : (a) )
#define max(a,b)                ((a)>(b) ? (a):(b))
#define ms(ara_name,value)      memset(ara_name,value,sizeof(ara_name))

/*************************** END OF TEMPLATE ****************************/

const int N = 300004 , LG = 19;
int n,m,S,sz;
vector<int> G[N];
int value[N];
vector<int>v;
int P[N][20], lev[N];
int root[N];
struct Node{ // Segment Tree node
    int ls,rs,cnt;
}node[N*20];

void update(int &n,int pre,int b,int e,int v)
{
    n = ++sz;
    node[n] = node[pre];
    if(b==e && b == v ) {
        node[n].cnt ++;
        return;
    }
    int mid = (b+e)/2;
    if(v <= mid ) update(node[n].ls, node[pre].ls, b,mid, v);
    else update(node[n].rs, node[pre].rs, mid+1,e, v);
    node[n].cnt = node[node[n].ls].cnt + node[node[n].rs].cnt;
}

int query(int r1,int r2,int r3,int r4, int b,int e,int k)
{
    if(b==e) return b;
    int oo = node[node[r1].ls].cnt + node[node[r2].ls].cnt - node[node[r3].ls].cnt - node[node[r4].ls].cnt ;

    int mid = (b+e)/2;

    if(oo >= k ) return query(node[r1].ls, node[r2].ls, node[r3].ls, node[r4].ls, b, mid, k);
    else return query(node[r1].rs, node[r2].rs, node[r3].rs, node[r4].rs, mid+1,e, k - oo );
}


void dfs(int u,int p)
{
    int Sz = G[u].size();
    for(int i = 0;i < Sz ; i ++ ){
        int a = G[u][i];
        if(a!=p) {
            update(root[a], root[u], 1, S, value[a] );
            lev[a] = 1 + lev[u];
            dfs(a,u);
            P[a][0] = u;
        }
    }
}
int lca(int u,int v)
{
    if(lev[u] > lev[v]) swap(u,v);
    int d = lev[v] - lev[u];
    for(int i = LG - 1; i >= 0 ;  i -- ) {
        if( d  &1<<i){
            v = P[v][i];
        }
    }

    if(u==v) return u;
    for(int i = LG-1; i >= 0 ; i -- ) {
        if(P[u][i] != P[v][i]) {
            u = P[u][i];
            v = P[v][i];
        }
    }
    return P[v][0];
}
int main()
{
    //freopen("in.txt","r",stdin);
    scanf("%d %d",&n,&m);
    for(int i = 1;i <= n; i ++) scanf("%d",&value[i]) , v.pb(value[i]);
    sort(all(v));
    v.resize(unique(all(v)) - v.begin());
    for(int i = 1; i <= n; i ++ ) value[i] = lower_bound(all(v),value[i]) - v.begin()  + 1;
    for(int i = 1; i <= n-1; i ++ ) {
        int a,b;
        scanf("%d %d",&a,&b);
        G[a].pb(b);
        G[b].pb(a);
    }
    ms(P,-1);
    S = v.size();
    update(root[1],0,1,S,value[1]);
    dfs(1,-1);

    for(int i = 1; i < LG;  i ++ ) {
        for(int j= 1; j <= n; j ++ ) {
            if(P[j][i-1] != -1) P[j][i] = P[P[j][i-1]][i-1];
        }
    }

    while(m--){
        int a,b,x;
        scanf("%d %d %d",&a,&b,&x);
        int lo = lca(a,b);

        int id = query(root[a],root[b], root[lo], P[lo][0] == -1 ? 0 : root[P[lo][0]] , 1 , S , x);
        printf("%d\n" , v[id-1]);
    }
    return 0;
}