Language: C++

// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2270

#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <functional>
#include <set>
#include <ctime>
#include <random>
#include <chrono>
#include <cassert>
using namespace std;

namespace {
  using Integer = long long; //__int128;
  template<class T> istream& operator >> (istream& is, vector<T>& vec){for(T& val: vec) is >> val; return is;}
  template<class T> istream& operator ,  (istream& is, T& val){ return is >> val;}
  template<class T> ostream& operator << (ostream& os, const vector<T>& vec){for(int i=0; i<vec.size(); i++) os << vec[i] << (i==vec.size()-1?"":" "); return os;}
  template<class T> ostream& operator ,  (ostream& os, const T& val){ return os << " " << val;}

  template<class H> void print(const H& head){ cout << head; }
  template<class H, class ... T> void print(const H& head, const T& ... tail){ cout << head << " "; print(tail...); }
  template<class ... T> void println(const T& ... values){ print(values...); cout << endl; }

  template<class H> void eprint(const H& head){ cerr << head; }
  template<class H, class ... T> void eprint(const H& head, const T& ... tail){ cerr << head << " "; eprint(tail...); }
  template<class ... T> void eprintln(const T& ... values){ eprint(values...); cerr << endl; }

  class range{
    long long start_, end_, step_;
   public:
    struct range_iterator{
      long long val, step_;
      range_iterator(long long v, long long step) : val(v), step_(step) {}
      long long operator * (){return val;}
      void operator ++ (){val += step_;}
      bool operator != (range_iterator& x){return step_ > 0 ? val < x.val : val > x.val;}
    };
    range(long long len) : start_(0), end_(len), step_(1) {}
    range(long long start, long long end) : start_(start), end_(end), step_(1) {}
    range(long long start, long long end, long long step) : start_(start), end_(end), step_(step) {}
    range_iterator begin(){ return range_iterator(start_, step_); }
    range_iterator   end(){ return range_iterator(  end_, step_); }
  };

  string operator "" _s (const char* str, size_t size){ return move(string(str)); }
  constexpr Integer my_pow(Integer x, Integer k, Integer z=1){return k==0 ? z : k==1 ? z*x : (k&1) ? my_pow(x*x,k>>1,z*x) : my_pow(x*x,k>>1,z);}
  constexpr Integer my_pow_mod(Integer x, Integer k, Integer M, Integer z=1){return k==0 ? z%M : k==1 ? z*x%M : (k&1) ? my_pow_mod(x*x%M,k>>1,M,z*x%M) : my_pow_mod(x*x%M,k>>1,M,z);}
  constexpr unsigned long long operator "" _ten (unsigned long long value){ return my_pow(10,value); }

  inline int k_bit(Integer x, int k){return (x>>k)&1;} //0-indexed

  mt19937 mt(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count());

  template<class T> string join(const vector<T>& v, const string& sep){
    stringstream ss; for(int i=0; i<v.size(); i++){ if(i>0) ss << sep; ss << v[i]; } return ss.str();
  }

  string operator * (string s, int k){ string ret; while(k){ if(k&1) ret += s; s += s; k >>= 1; } return ret; }

}



inline int pop_count(unsigned long long x){
  x = (x & 0x5555555555555555UL) + (x >>  1 & 0x5555555555555555UL);
  x = (x & 0x3333333333333333UL) + (x >>  2 & 0x3333333333333333UL);
  x = (x & 0x0f0f0f0f0f0f0f0fUL) + (x >>  4 & 0x0f0f0f0f0f0f0f0fUL);
  x = (x & 0x00ff00ff00ff00ffUL) + (x >>  8 & 0x00ff00ff00ff00ffUL);
  x = (x & 0x0000ffff0000ffffUL) + (x >> 16 & 0x0000ffff0000ffffUL);
  x = (x & 0x00000000ffffffffUL) + (x >> 32 & 0x00000000ffffffffUL);
  return x;
}
class BitVector{
 public:
  vector<long long> TR;   // compressed 01 bit array
  vector<int> TL;   // large table contains count of 1-bits
  vector<int> TS;   // small table contains count of 1-bits
  //vector<long long> TS_bit;   // bit-parallel

  size_t bit_L = 9;
  size_t bit_S = 6;

  size_t size_L = 1<<9;
  size_t size_S = 1<<6;

  int lg_size;

  int count_one  = 0;
  int count_zero = 0;

  BitVector(vector<int>& v){
    TL.resize( (v.size() + size_L - 1) >> bit_L , 0);
    TS.resize( TL.size() * (size_L / size_S) , 0);
    TR.resize( TL.size() * (size_L / size_S)  , 0);

    for(int i=0; i<v.size(); i++){
      TR[i >> bit_S] |= (long long)(v[i]) << (i&0b111111);
      if((i >> bit_S) + 1 < TS.size()) TS[(i >> bit_S) + 1] += v[i];
      if((i >> bit_L) + 1 < TL.size()) TL[(i >> bit_L) + 1] += v[i];

      (v[i] ? count_one : count_zero) += 1;
    }
    for(int i=1; i<TL.size(); i++){
      TL[i] += TL[i-1];
    }
    for(int i=1; i<TS.size(); i++){
      if(i % (size_L / size_S)) TS[i] += TS[i-1];
      else TS[i] = 0;
    }
    /*
    TS_bit.resize( TL.size(), 0);
    for(int i=0; i<TR.size(); i++){
      long long d = pop_count(TR[i]);
      TS_bit[ i >> 3 ] |= d << ((i & 7) * 7);
    }
    */

    lg_size = 0;
    while( 1<<(lg_size+1) < (TL.size()-1)) lg_size++;
  }

  int at(int pos){
    assert(0 <= pos && pos < count_one + count_zero);
    return (TR[ pos >> bit_S ] >> (pos & 0x11111)) & 1;
  }

  //count of q in [0, ub)
  int rank(int q, int ub){
    int res = 0;

    res += TL[ ub>>bit_L ];
    res += TS[ ub>>bit_S ];
    
    unsigned long long mask = (1LL << ( ub & (size_S-1) )) - 1;
    res += pop_count(TR[ (ub>>bit_S) ] & mask);

    if(q == 0) res = ub - res;
    return res;
  }

  //the position + 1 of the t+1-th occurrence of q
  // rank(q, select(q, t)) = t
  int select(int q, int t){
    if( (q ? count_one : count_zero) <= t) return -1;

    t++;
    int idx_L = binary_search_L(q, t);

    int idx_S = binary_search_S(q, t, idx_L);

    int idx_R = binary_search_R(q, t, idx_S);

    int ret = idx_S * size_S + idx_R;
    return ret;
  }

 private:

  inline int binary_search_L(int q, int& t){
    /*
    int lb = 0;
    int ub = TL.size();
    while(ub - lb > 1){
      int mid = (lb + ub) >> 1;
      int cnt = q ? TL[mid] : mid * size_L - TL[mid];
      (cnt < t? lb : ub) = mid;
    }
    t -= q ? TL[lb] : lb*size_L - TL[lb];
    return lb;
    */

    int tmp = 0;
    for(int k=lg_size, sm=0; k>=0; k--){
      if(sm == 0 && (((TL.size()-1)>>k)&1)==0) continue;
      int cnt = TL[tmp + (1<<k)];
      if(!q) cnt = (tmp+(1<<k)) * size_L - cnt;
      if(cnt < t) tmp += 1<<k;
      else sm = 1;
    }
    int cnt = TL[tmp];
    if(!q) cnt = (tmp) * size_L - cnt;
    t -= cnt;
    return tmp;
  }

  inline int binary_search_S(int q, int& t, int& idx_L){
    /*{
      int ub = (idx_L + 1) * size_L / size_S;
      int lb = idx_L * size_L / size_S;
      int ll = lb;
      while(ub - lb > 1){
        int mid = (lb + ub) >> 1;
        int cnt = q ? TS[mid] : (mid-ll)*size_S - TS[mid];
        (cnt < t? lb : ub) = mid;
      }

      t -= q ? TS[lb] : (lb-ll)*size_S - TS[lb];
      return lb;
    }*/
    

    {
      int ret = idx_L * size_L / size_S;
      int tmp = 0;
      for(int k=2; k>=0; k--){
        int cnt = TS[ret + tmp + (1<<k)];
        if(!q) cnt = (tmp+(1<<k)) * size_S - cnt;
        if(cnt < t){
          tmp += (1<<k);
        }
      }
      int cnt = TS[ret + tmp];
      if(!q) cnt = tmp * size_S - cnt;
      t -= cnt;

      return ret + tmp;
    }
    /*
    {
      long long a = TS_bit[ idx_L ];
      long long b = (a & 0x01fc07f01fc07fUL) + (a >>   7 & 0x01fc07f01fc07fUL);
      long long c = (b & 0x0003fff0003fffUL) + (b >>  14 & 0x0003fff0003fffUL);

      int k = 0;
      int cnt = c & 0xfffffff;
      if(!q) cnt = (64<<2) - cnt;
      if(cnt < t){
        t -= cnt;
        k += 4;
      }
      b = (b >> (k*7)) & 0xfffffff;

      cnt = b & 0x0003fff;
      if(!q) cnt = (64<<1) - cnt;
      if(cnt < t){
        t -= cnt;
        k += 2;
      }
      a = (a >> (k*7)) & 0x0003fff;

      cnt = a & 0x7f;
      if(!q) cnt = 64 - cnt;
      if(cnt < t){
        t -= cnt;
        k += 1;
      }
      return k + idx_L * size_L / size_S;
    }
    */
  }

  inline int binary_search_R(int q, int& t, int idx_S){
    long long a = TR[ idx_S ];
    if(!q) a = ~a;

    /*
    int lb = 0;
    int ub = 64;
    while(ub-lb > 1){
      int mid = (ub+lb) >> 1;
      int cnt = pop_count(a & ((1LL<<mid) - 1));
      (cnt<t ? lb : ub) = mid;
    }
    return lb;
    */
    long long b = (a & 0x5555555555555555UL) + (a >>  1 & 0x5555555555555555UL);
    long long c = (b & 0x3333333333333333UL) + (b >>  2 & 0x3333333333333333UL);
    long long d = (c & 0x0f0f0f0f0f0f0f0fUL) + (c >>  4 & 0x0f0f0f0f0f0f0f0fUL);
    long long e = (d & 0x00ff00ff00ff00ffUL) + (d >>  8 & 0x00ff00ff00ff00ffUL);
    long long f = (e & 0x0000ffff0000ffffUL) + (e >> 16 & 0x0000ffff0000ffffUL);

    int k = 0;

    if( (f & 0xffffffff) < t ){
      t -= (f & 0xffffffff);
      k += 32;
    }
    e = (e>>k) & 0xffff;

    if( (e & 0xffff) < t){
      t -= (e & 0xffff);
      k += 16;
    }
    d = (d>>k) & 0xff;

    if( (d & 0xff) < t){
      t -= (d & 0xff);
      k += 8;
    }
    c = (c>>k) & 0xf;

    if( (c & 0xf) < t){
      t -= (c & 0xf);
      k += 4;
    }
    b = (b>>k) & 0x3;

    if( (b & 0x3) < t){
      t -= (b & 0x3);
      k += 2;
    }
    a = (a>>k) & 0x1;


    if( (a & 0x1) < t){
      t -= (a & 0x1);
      k += 1;
    }

    return k;
  }
};

// T = unsigned int / unsigned long long
// B = bitvector container type
template<class T, class B>
class WaveletMatrix{
  vector<B> m;
  vector<int> L_size;
  T lg;
  const int len;
 public:
  WaveletMatrix(vector<T>& v) : len(v.size()){
    T mx = *max_element(v.begin(), v.end());
    lg = 0;
    while((T(1)<<lg+1) < mx) lg++;

    m.reserve(lg+1);
    L_size.resize(lg+1);

    deque<int> l,r;

    l.resize(len);
    iota(l.begin(), l.end(), 0);

    for(int k=0; k<=lg; k++){
      deque<int> l_, r_;
      vector<int> bits(len);

      L_size[k] = l.size();

      for(int i=0; i<l.size(); i++){
        bits[i] = (v[ l[i] ] >> (lg-k))&1;
        if( (v[ l[i] ] >> (lg-k))&1 ){
          r_.push_back( l[i] );
        }else{
          l_.push_back( l[i] );
        }
      }

      for(int i=0; i<r.size(); i++){
        bits[l.size() + i] = (v[ r[i] ] >> (lg-k))&1;
        if( (v[ r[i] ] >> (lg-k))&1 ){
          r_.push_back( r[i] );
        }else{
          l_.push_back( r[i] );
        }
      }

      swap(l, l_);
      swap(r, r_);
      m.emplace_back(bits);

      /*
      for(int i=0; i<len; i++){
        cerr << bits[i];
      }cerr << endl;
      */
    }
  }

  //return count of the occurence of q in [0, ub)
  int rank(T q, int ub, int lb=0, int k=0){
    if(q >= (T(1)<<lg+1)) return 0;
    //ub = min(len, ub);
    int bit = (q>>lg-k) & 1;
    int r = m[k].rank(bit, ub);
    int l = m[k].rank(bit, lb);
    if(k==lg) return r - l;
    if(bit == 0){
      return rank(q, r, l, k+1);
    }else{
      return rank(q, L_size[k+1] + r, L_size[k+1] + l, k+1);
    }
  }

 private:
  int rank_less_than_(T q, int lb, int ub, int k=0){
    int res = 0;
    int bit = (q>>lg-k) & 1;
    int r = m[k].rank(bit, ub);
    int l = m[k].rank(bit, lb);
    if(bit == 1){
      res += ub-lb - (r-l);
    }
    if(k==lg) return res + r - l;
    if(bit == 0){
      return res + rank_less_than_(q, l, r, k+1);
    }else{
      return res + rank_less_than_(q, L_size[k+1] + l, L_size[k+1] + r, k+1);
    }
  }

 public:
  int rank_less_than(T q, int lb, int ub){
    if(ub<=lb) return 0;
    if(q >= (T(1)<<lg+1)) return ub-lb;
    return rank_less_than_(q, lb, ub, 0);
  }

 private:
  int select(T q, int t, int lb, int ub, int k){
    int bit = (q>>lg-k) & 1;

    int r = m[k].rank(bit, ub);
    int l = m[k].rank(bit, lb);

    if(k==lg){
      return (r-l > t) ? m[k].select(bit, l+t) : -1;
    }else{
      if(bit == 0){
        t = select(q, t, l,r, k+1);
      }else{
        t = select(q, t, L_size[k+1] + l, L_size[k+1] + r, k+1) - L_size[k+1];
      }
      if(t <= -1) return -1;
      
      return m[k].select(bit, t);
    }
  }

 public:
  //return t-th occurence position of q
  //if q is not in the list then return -1
  int select(T q, int t){
    if(q >= (T(1)<<lg+1)) return -1;
    return select(q,t, 0,len, 0);
  }


  //return (t+1)-th biggest {value, pos} in [lb,ub)
  pair<int,int> quantile(int lb, int ub, int t, int k=0){
    if(t >= ub-lb) return {-1,-1};

    int val = 0;
    int pos = lb;

    int r = m[k].rank(1, ub);
    int l = m[k].rank(1, lb);

    if(k==lg){
      if(r-l > t){
        pos = m[k].select(1, r-1 - t);
        return {1, pos};
      }else{
        pos = m[k].select(0, ub-1-t-l );
        return {0, pos};
      }
    }
    if( r-l > t ){
      auto tmp = quantile(L_size[k+1] + l, L_size[k+1] + r, t, k+1);
      val = (T(1)<<(lg-k)) | tmp.first;
      pos = m[k].select(1, tmp.second - L_size[k+1]);
    }else{
      auto tmp = quantile(lb-l, ub-r, t-(r-l), k+1);
      val = tmp.first;
      pos = m[k].select(0, tmp.second);
    }
    return {val, pos};
  }
};

void Eular_tour(vector<vector<int>>& G, int pos, int last, vector<int>& res){
  res.push_back(pos);
  for(int nx : G[pos]){
    if(nx == last) continue;
    Eular_tour(G, nx, pos, res);
  }
  res.push_back(pos);
}


class LCA{

  int root;
  //depth of node[i]
  vector<int> d;
  
  //parent of node[i]
  vector<vector<int> > p;

  
  int size;
  
  //initialization of depths and parents
  void init(vector<vector<int> > &g, int pos, int last, int v){
    d[pos] = v;
    p[0][pos] = last;
    for(int i=0; i<g[pos].size(); i++){
      if(g[pos][i] == last) continue;
      init(g, g[pos][i], pos, v+1);
    }
  }

 public:

  //vector<vector<int> >
  //g[i][j] := node[i]'s edge gose to node[ g[i][j] ]
  
  LCA(vector<vector<int> > &g, int r){
    int n = g.size();
    root = r;
    d = vector<int>(n);

    size = 1;
    while((1<<size) <= n){
      size++;
    }
    
    p = vector<vector<int> >(size, vector<int>(n));
    
    init(g, root,-1,0);
    
    for(int k=0; k+1 < size; k++){
      for(int v=0; v<n; v++){
        if(p[k][v] < 0) p[k+1][v] = -1;
        else p[k+1][v] = p[k][p[k][v]];
      }
    }
  }
  
  LCA(vector<vector<int> > &g){
    int n = g.size();
    root = 0;
    d = vector<int>(n);
    size = 1;
    while((1<<size) <= n){
      size++;
    }
    p = vector<vector<int> >(size, vector<int>(n));

    //initialize as root = 0
    init(g, root,-1,0);
    
    for(int k=0; k+1 < size; k++){
      for(int v=0; v<n; v++){
        if(p[k][v] < 0) p[k+1][v] = -1;
        else p[k+1][v] = p[k][p[k][v]];
      }
    }
  }
  
  //return the node number of lowest common ancestor between u and v
  int get_lca(int u, int v){
    if(d[u] > d[v]) swap(u,v);
    for(int k=0; k<size; k++){
      if( (d[v] - d[u]) >> k & 1){
        v = p[k][v];
      }
    }
    if(u==v) return u;

    for(int k=size-1; k>=0; k--){
      if(p[k][u] != p[k][v]) {
        u = p[k][u];
        v = p[k][v];
      }
    }
    return p[0][u];
  }

  //return depth of node[u]
  int depth(int u){
    return d[u];
  }
};

template<class T>
vector<T> compress(vector<T> a, vector<T>& b){
  b = a;
  sort(b.begin(), b.end());
  b.erase( unique(b.begin(), b.end()), b.end());
  for(int i=0; i<a.size(); i++){
    a[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
  }
  return a;
}

int main(){
  int n,q;
  cin >> n,q;
  vector<int> v(n);
  for(auto&& x: v) scanf("%d", &x);
  vector<vector<int>> G(n);
  for(int i : range(n-1)){
    int a,b;
    scanf("%d%d", &a, &b);
    a--; b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }

  vector<int> E;
  Eular_tour(G, 0, 0, E);

  v.push_back(9_ten + 1);
  vector<int> dic;
  auto v_c = compress(v, dic);

  vector<int> in(n, -1);
  vector<int> x,y;
  for(auto i : E){
    if(in[i] != -1){
      x.push_back(dic.size() - 1);
      y.push_back(v_c[i]);
    }else{
      in[i] = x.size();
      x.push_back(v_c[i]);
      y.push_back(dic.size() - 1);
    }
  }

  WaveletMatrix<int, BitVector> w_x(x);
  WaveletMatrix<int, BitVector> w_y(y);

  LCA lca(G, 0);

  while(q--){
    int a,b,c;
    scanf("%d%d%d", &a, &b, &c);
    a--; b--;

    int p = lca.get_lca(a,b);

    auto check = [&](int k){  //count x[i] < k | i in the range
      
      int ai = w_x.rank_less_than(k, in[p],in[a]+1);
      int ao = w_y.rank_less_than(k, in[p],in[a]+1);

      int bi = w_x.rank_less_than(k, in[p]+1,in[b]+1);
      int bo = w_y.rank_less_than(k, in[p]+1,in[b]+1);

      int cnt  = ai-ao + bi-bo;

      int cnt_ = 0;
      int ai_,ao_,bi_,bo_;
      ai_ = ao_ = bi_ = bo_ 0;
      for(int i=in[p]; i<=in[a]; i++){
        if(x[i] <= k) ai_++;
      }
      for(int i=in[p]; i<=in[a]; i++){
        if(y[i] <= k) ao_++;
      }
      for(int i=in[p]+1; i<=in[b]; i++){
        if(x[i] <= k) bi_++;
      }
      for(int i=in[p]+1; i<=in[b]; i++){
        if(y[i] <= k) bo_++;
      }

      assert(ai == ai_);
      //assert(bi == bi_);
      //assert(ao == ao_);
      //assert(bo == bo_);

      cnt_ = ai_ + bi_ - ao_ - bo_;
      //assert(cnt_ == cnt);
      

      return cnt_;
    };
    
    int lb = -1;
    int ub = dic.size()-2;
    while(ub-lb>1){
      int mid = (lb+ub)>>1;
      int cnt = check(mid);
      (cnt < c? lb : ub) = mid;
    }
    
    /*
    int ub = 0;
    for(; ub<dic.size(); ub++){
      int cnt = check(ub);
      if(cnt >= c) break;
    }
    */

    printf("%d\n", dic[ub]);
  }
  return 0;
}

Compiler output:
a.cc: In lambda function:
a.cc:654:28: error: expected ';' before numeric constant
  654 |       ai_ = ao_ = bi_ = bo_ 0;
      |                            ^~
      |                            ;