This is a wizardy solution from the last problem of Week of Code 34 which I found, author nickname: @FMota0

fmota-path-statistics.cpp

#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
#define left fdhfkladhfl
#define right fdflhdlfjha
#define tm fadfdhajl
using namespace std;
const int maxn = 55555;
struct bset{
    vector<long long> info;
    bset(){}
    bset(int n){
        resize(n);
    }
    void resize(int n){
        n++;
        info.resize((n + 63)>>6);
        for(long long &v : info) v = 0;
    }
    void set(int pos){
        info[pos>>6] |= (1ll<<(pos&((1<<6)-1)));
    }
    void flip(int pos){
        info[pos>>6] ^= (1ll<<(pos&((1<<6)-1)));
    }
    bool get(int pos){
        return ((info[pos>>6])>>(pos&((1<<6)-1)))&1;
    }
    bset operator | (bset & other){
        bset ans(info.size());
        for(int e = 0; e < info.size(); e++)
            ans.info[e] = info[e] | other.info[e];
        return ans;
    }
    void OR(bset & other){
        for(int e = 0; e < info.size(); e++)
            info[e] |= other.info[e];
    }
    bset copy(){
        bset ans = *this;
        return ans;
    }
};
const int lc = 20;
vector<int> g[maxn];
int st[maxn], en[maxn], on[3*maxn], tm;
int lca[lc][maxn], depth[maxn];
void dfs(int cur, int pr){
    lca[0][cur] = pr;
    st[cur] = tm;
    on[tm++] = cur;
    for(int lg = 1; lg < lc; lg++){
        if(lca[lg-1][cur] != -1){
            lca[lg][cur] = lca[lg-1][lca[lg-1][cur]];
        }
    }
    for(int v : g[cur]) if (v != pr){
        depth[v] = depth[cur] + 1;
        dfs(v, cur);
    }
    en[cur] = tm;
    on[tm++] = cur;
}
int getLca(int u, int v){
    if(depth[u] < depth[v]) swap(u, v);
    for(int lg = lc-1; lg >= 0; lg--)
        if((depth[u] - depth[v])&(1<<lg))
            u = lca[lg][u];
    if(u == v)
        return u;
    for(int lg = lc-1; lg >= 0; lg--)
        if(lca[lg][u] != lca[lg][v]){
            u = lca[lg][u];
            v = lca[lg][v];
        }
    return lca[0][u];
}
int BL[3*maxn], md = 270;
struct query{
    int id, l, r, lc, kth;
    bool operator < (const query other) const {
		return (BL[l] == BL[other.l]) ? (r < other.r) : (BL[l] < BL[other.l]);
    }
};
int sum[maxn];
int values[maxn], ans[maxn];
int cnt[maxn], times[maxn], comp;
vector<bset> demencia;
void alter(int pos){
    int v = values[pos];
    if(times[pos] == 0){
        sum[cnt[v]]--;
        demencia[cnt[v]].flip(v);
        cnt[v]++;
        demencia[cnt[v]].set(v);
    } else {
        demencia[cnt[v]].flip(v);
        cnt[v]--;
        demencia[cnt[v]].set(v);
        sum[cnt[v]]++;
    }
    times[pos] ^= 1;
}
const int bitcount = 1<<22;
int popcount[bitcount];
int count(long long v){
    int ans = 0;
    while(v){
        ans += popcount[v & (bitcount - 1)];
        v >>= 22;
    }
    return ans;
}
int n, q;
int getAns(int kth){
    int lo = 1, hi = n, ans = -1;
    while(lo <= hi){
        int mid = (lo + hi)>>1;
        if(sum[maxn-1] - sum[mid-1] >= kth) ans = mid, lo = mid + 1;
        else hi = mid - 1;
    }
    int need = kth - sum[maxn-1] + sum[ans];
    // printf("bin %d %d\n", kth, need);
    int pos = demencia[ans].info.size() * 64;
    int len = demencia[ans].info.size();
    for(int e = len-1; e >= 0; e--){
        int here = __builtin_popcountll(demencia[ans].info[e]);
        // printf("%d %d\n", e, here);
        if(here >= need){
            pos --;
            for(int f = pos; f >= pos - 63; f--){
                if(demencia[ans].get(f)){
                    if(need == 1) {
                        // printf("res %d\n", f);
                        return f;
                    }
                    need--;
                }
            }
        }
        pos -= 64;
        need -= here;
    }
    return 1;
}
int main(){
    for(int e = 1; e < bitcount; e++) popcount[e] = popcount[e - (e & - e)] + 1;
    scanf("%d %d", &n, &q);
    md = sqrt(n) + 1;
    for(int e = 1; e < 3*maxn; e++) BL[e] = e / md + 1;
    vector<int> compress;
    for(int e = 0; e < n; e++)
        scanf("%d", values + e), compress.push_back(values[e]);
    sort(compress.begin(), compress.end());
    compress.erase(unique(compress.begin(), compress.end()), compress.end());
    for(int e = 0; e < n; e++)
        values[e] = lower_bound(compress.begin(), compress.end(), values[e]) - compress.begin() + 1;
    comp = compress.size();

    demencia.resize(n + 1);
    for(int e = 0; e < n + 1; e++)
        demencia[e].resize(comp);
    for(int e = 1; e <= comp; e++)
        demencia[0].set(e);

    sum[0] = n;
    for(int e = 1; e < maxn; e++)
        sum[e] = n;

    for(int e = 0; e < n-1; e++){
        int u, v; scanf("%d %d", &u, &v);
        u--; v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs(0, -1);
    // for(int e = 0; e < n; e++)
    //     printf("%d : (%d, %d) -> %d\n", e, st[e], en[e], values[e]);
    vector<query> queries;
    for(int e = 0; e < q; e++){
        int from, to, kth;
        scanf("%d %d %d", &from, &to, &kth);
        from--; to--;
        query cur;
        cur.lc = getLca(from, to);
        // printf("lca %d\n", cur.lc);
        if(st[from] > st[to]) swap(from, to);
        if(cur.lc == from) cur.l = st[from], cur.r = st[to];
        else cur.l = en[from], cur.r = st[to];
        cur.id = e;
        cur.kth = kth;
        queries.push_back(cur);
    }

    sort(queries.begin(), queries.end());

    // tree::init();
    int curL = queries[0].l, curR = queries[0].l - 1;
    for(int e = 0; e < queries.size(); e++){
        while(curL < queries[e].l) alter(on[curL++]);
        while(curL > queries[e].l) alter(on[--curL]);
        while(curR < queries[e].r) alter(on[++curR]);
        while(curR > queries[e].r) alter(on[curR--]);
        int u = on[curL], v = on[curR];
        if(queries[e].lc != u && queries[e].lc != v) alter(queries[e].lc);
        ans[queries[e].id] = compress[getAns(queries[e].kth)-1];

        // if(u == 0 && v == 1){
        //     for(int c = 0; c < 5; c++)
        //         printf("%d : %d\n", c, sum[c]);
        // }
        if(queries[e].lc != u && queries[e].lc != v) alter(queries[e].lc);
    }
    for(int e = 0; e < queries.size(); e++)
        printf("%d\n", ans[e]);
    return 0;
}