Arvore.cpp

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

const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
// #define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

#define maxn 500010

int n, q, a[maxn], tr[30*maxn], lc[23*maxn], rc[23*maxn], beg[maxn], p[maxn][23], h[maxn], pai[maxn], ccval[maxn];
int nocur = 0;
vector<int> g[maxn];


int build(int no, int l, int r) {
    if(no == 0) no = ++nocur;

    if(l == r) {
        tr[nocur] = 0;
        return no;
    }

    int mid = (l+r)/2;
    lc[no] = build(lc[no],l,mid);
    rc[no] = build(rc[no],mid+1,r);

    return no;
}

int att(int ant, int no, int l, int r, int pos, int val) {
    if(no == 0) no = ++nocur;

    if(l == r) {
        tr[no] = tr[ant] + val;
    }
    else {
        int mid = (l+r)/2;

        if(pos <= mid) {
            if(lc[no] == 0) lc[no] = ++nocur;
            if(rc[no] == 0) rc[no] = rc[ant];

            lc[no] = att(lc[ant],lc[no],l,mid,pos,val);
            rc[no] = rc[ant];
        }
        else {
            rc[no] = att(rc[ant],rc[no],mid+1,r,pos,val);
            lc[no] = lc[ant];
        }

        tr[no] = tr[lc[no]]+tr[rc[no]];
    }

    return no;
}

int qrr(int v1, int v2, int v3, int v4, int l, int r, int val) {
    if(l == r) {
        return l;
    }

    int mid = (l+r)/2;
    int slf = tr[lc[v1]]+tr[lc[v2]]-tr[lc[v3]]-tr[lc[v4]];
    if(val-slf <= 0) {
        //vai pra esquerda
        return qrr(lc[v1],lc[v2],lc[v3],lc[v4],l,mid,val);
    }
    else {
        return qrr(rc[v1],rc[v2],rc[v3],rc[v4],mid+1,r,val-slf);
    }
}

void dfs(int u, int ant) {
    pai[u] = ant;
    beg[u] = att(beg[ant],0,1,n,a[u],1);

    for(auto v : g[u]) {
        if(v == ant) continue;
        dfs(v,u);
    }
}

void dfslca(int u, int ant) {
    p[u][0] = ant;
    for(int i = 1; i <= 20; i++) {
        p[u][i] = p[p[u][i-1]][i-1];
    }

    for(auto v : g[u]) {
        if(v == ant) continue;
        h[v] = h[u]+1;
        dfslca(v,u);
    }
}

int lca(int u, int v) {
    if(h[u] < h[v]) swap(u,v);

    for(int i = 20; i >= 0; i--) {
        if(h[p[u][i]] >= h[v]) {
            u = p[u][i];
        }
    }

    if(u == v) {
        return u;
    }
    for(int i = 20; i >= 0; i--) {
        if(p[u][i] != p[v][i]) {
            u = p[u][i];
            v = p[v][i];
        }
    }

    return p[u][0];
}

void solve() {
    cin >> n >> q;

    vector<int> cc;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        cc.pb(a[i]);
    }

    sort(all(cc));
    cc.erase(unique(all(cc)),cc.end());

    for(int i = 1; i <= n; i++) {
        int val = upper_bound(all(cc),a[i]) - cc.begin();
        ccval[val] = a[i];
        a[i] = val;
    }

    for(int i = 0; i < n-1; i++) {
        int u, v; cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }

    beg[0] = 1;
    nocur = 1;
    build(1,1,n);
    dfs(1,0);
    dfslca(1,1);

    while(q--) {
        int u,v,k; cin >> k >> u >> v;
        int lc = lca(u,v);

        cout << ccval[qrr(beg[u],beg[v],beg[lc],beg[pai[lc]],1,n,k)] << endl;
    }
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    //freopen("out.out", "w", stdout);
    
    int tt = 1;
    // cin >> tt;
    while(tt--) solve();

}