kth number on path

#include <bits/stdc++.h>
#define x first
#define y second
#define pii pair<int,int>
using ll=long long;
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define vl vector<ll>
#define all(a) begin(a),end(a)

using namespace std;

const int N=100010,M=1<<17;
int q,n,de[N],par[20][N],nod[N],cn[N],req[N],seg[M*2+10];
ll h[N];
vi ch[N];
vector<pii> ord,qu[N];

void dfs(int i,int p=0)
{
    par[0][i]=p;
    ord.pb({i,1});
    for (auto a: ch[i]) if (a!=p) de[a]=de[i]+1,dfs(a,i);
    ord.pb({i,-1});
}

int lca(int a,int b)
{
    for (int j=17;j>=0;--j) if (de[a]-de[b]>=(1<<j)) a=par[j][a];
    for (int j=17;j>=0;--j) if (de[b]-de[a]>=(1<<j)) b=par[j][b];
    if (a==b) return a;
    for (int j=17;j>=0;--j) if (par[j][a]!=par[j][b]) a=par[j][a],b=par[j][b];
    return par[0][a];
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>q;
    vl v;
    for (int i=0;i<n;++i) cin>>h[i],v.pb(h[i]);
    sort(all(v));
    v.erase(unique(all(v)),v.end());
    for (int i=0;i<n;++i) h[i]=lower_bound(all(v),h[i])-v.begin();
    for (int i=1;i<n;++i)
    {
        int a,b;
        cin>>a>>b;
        --a;
        --b;
        ch[a].pb(b);
        ch[b].pb(a);
    }
    dfs(0);
    for (int j=1;j<18;++j) for (int i=0;i<n;++i) par[j][i]=par[j-1][par[j-1][i]];
    for (int i=0;i<q;++i)
    {
        int a,b;
        cin>>a>>b>>req[i];
        --a;
        --b;
        qu[a].pb({i,1});
        qu[b].pb({i,1});
        int z=lca(a,b);
        qu[z].pb({i,-1});
        if (z) qu[par[0][z]].pb({i,-1});
        nod[i]=1;
    }
    for (int z=16;z>=0;--z)
    {
        for (int i=0;i<q;++i) nod[i]*=2;
        memset(cn,0,sizeof(cn));
        for (auto x: ord)
        {
            seg[(h[x.x]+M)>>z]+=x.y;
            if (x.y==1) for (auto a: qu[x.x])
            {
                cn[a.x]+=a.y*seg[nod[a.x]];
            }
        }
        for (int i=0;i<q;++i)
        {
            if (cn[i]<req[i])
            {
                req[i]-=cn[i];
                ++nod[i];
            }
        }
    }
    for (int i=0;i<q;++i) cout<<v[nod[i]-M]<<'\n';
}