Language: C++

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <cstring>
#include <numeric>
#include <algorithm>
#include <functional>
#include <array>
#include <map>
#include <queue>
#include <limits.h>
#include <set>
#include <stack>
#include <random>
#include <complex>
#include <unordered_map>
#include <nmmintrin.h>
#include <chrono>
#define rep(i,s,n) for(int i = (s); (n) > i; i++)
#define REP(i,n) rep(i,0,n)
#define RANGE(x,a,b) ((a) <= (x) && (x) <= (b))
#define DUPLE(a,b,c,d) (RANGE(a,c,d) || RANGE(b,c,d) || RANGE(c,a,b) || RANGE(d,a,b))
#define INCLU(a,b,c,d) (RANGE(a,c,d) && (b,c,d))
#define PW(x) ((x)*(x))
#define ALL(x) (x).begin(), (x).end()
#define MODU 1000000007
#define bitcheck(a,b)   ((a >> b) & 1)
#define bitset(a,b)      ( a |= (1 << b))
#define bitunset(a,b)    (a &= ~(1 << b))
#define MP(a,b) make_pair((a),(b))
#define Manh(a,b) (abs((a).first-(b).first) + abs((a).second - ((b).second))
#define pritnf printf
#define scnaf scanf
#define itn int
#ifdef _MSC_VER
#define __builtin_popcount _mm_popcnt_u32
#define __builtin_popcountll _mm_popcnt_u64
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a%b);
}
template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T &val) {
	std::fill((T*)array, (T*)(array + N), val);
}

class Graph {
public:
	int vn;
	int sumcost = 0;
	vector<vector<pii>> g;

	Graph(int n) {
		vn = n;
		g.resize(n);
	}
	virtual void con(int a, int b, int w) = 0;
	int getWeight(int f, int t) {
		auto itr = lower_bound(ALL(g[f]), make_pair(t, INT_MIN));
		if (itr != g[f].end())
			return itr->second;
		return INT_MIN;
	}
	int Costsum() {
		return sumcost;
	}
	void scan(int edcount, bool oindexed, bool w) {
		REP(i, edcount) {
			int a, b, c = 1;
			scanf("%d %d", &a, &b);
			if (w)scanf("%d", &c);
			con(a - oindexed, b - oindexed, c);
		}
	}
};
class BiDGraph : public Graph {//??????
public:
	BiDGraph(int n) : Graph(n) {}

	void con(int a, int b, int w = 1) {
		g[a].push_back({ b,w });
		g[b].push_back({ a, w });
		sumcost++;
	}
};
class DGraph : public Graph {//??????
public:
	DGraph(int n) : Graph(n) {}
	void con(int a, int b, int w = 1) {
		g[a].push_back({ b,w });
		sumcost++;
	}
};
class Bitvector {
	//4byte???????????? ??¨??¨?????????0-index
	static const int mask[32];
public:

	unsigned int* st;
	unsigned __int8* blockrank;
	int sz;
	Bitvector(int n) {
		sz = n;
		st = (unsigned int*)calloc((n + 31) / 32, sizeof(int));
		blockrank = (unsigned __int8*)calloc((n + 7) / 8 + 1, sizeof(__int8));
		if (st == NULL || blockrank == NULL)
			abort();
	}
	inline void set(int a, bool f) {//????????????????????§?????????
		if (f)bitset(st[a / 32], (31 - a % 32));
	}
	inline bool get(int a) { return bitcheck(st[a / 32], (31 - a % 32)); }
	inline void calcblock() {
		int cou = 0;
		REP(i, sz + 1) {
			if (i && !(i % 8))blockrank[i / 8] = cou;
			if (i<sz)cou += bitcheck(st[i / 32], (31 - i % 32));
		}
	}
	inline int rank(int a, bool t) {
		int ret = blockrank[a / 8] + (((8 - a % 8) >= 8) ? 0 : __builtin_popcount((st[a / 32] << (a/8)*8)>> (a / 8) * 8+(32 - a % 32)));
		return t ? ret : a - ret;
	}
	int select(int a, bool t) {
		int l = 0, r = sz + 1;

		while (r - l > 1) {
			int mid = (l + r) / 2;
			if (rank(mid, t) >= a) r = mid;
			else l = mid;
		}
		if (rank(r, t) < a) return -1;
		return r;
	}
	void clear() {
		free(st);
		free(blockrank);
	}
};


//??????????????£??????????????????????????????(?????¬????????§????????¶????????§)
template<typename T>
class WaveletMatrix {
public:
	vector<T> data;
	vector<Bitvector> bitv;
	vector<int> border;
	int Max = 0;
	int bitsize;
	WaveletMatrix(vector<T>& dat) : bitsize(sizeof(T) * 8), data(dat) {
		bitv.reserve(bitsize);
		REP(i, bitsize + 1)
			bitv.push_back(Bitvector(data.size()));
		border.resize(bitsize + 1);
		REP(j, data.size())
			Max = max(Max, data[j]), bitv[0].set(j, bitcheck(data[j], bitsize - 1));
		bitv[0].calcblock();
		vector<T> buf[2];
		buf[0] = data;
		buf[1].resize(data.size());

		REP(i, bitsize - 1) {
			border[i + 1] = bitv[i].rank(data.size(), 0);
			int cou[2] = { 0, border[i + 1] };
			REP(j, data.size()) {
				bitv[i + 1].set(cou[bitv[i].get(j)], bitcheck(buf[i % 2][j], bitsize - i - 2));
				buf[1 - i % 2][cou[bitv[i].get(j)]] = buf[i % 2][j] << (i + 1) >> (i + 1);
				cou[bitv[i].get(j)]++;
			}
			bitv[i + 1].calcblock();
		}
		border[bitsize] = bitv[bitsize - 1].rank(data.size(), 0);
		sort(ALL(data));
	}

	pii search(int s, int e, unsigned int t, int b = 0) {
		if (b == bitsize) return{ s,e };
		bool cur = bitcheck(t, bitsize - 1);
		return search(cur*border[b + 1] + bitv[b].rank(s, cur), cur*border[b + 1] + bitv[b].rank(e, cur), t << 1, b + 1);
	}
	int backward(int a, unsigned int t, int b = 0) {
		if (b == bitsize - 1) return a;
		backward(bitv[bitsize - b - 1].select(a + 1 - bitcheck(t, 0) * border[bitsize - b], bitcheck(t, 0)) - 1, t >> 1, b + 1);
	}

	int rank(int s, int e, T t) {
		pii r = search(s, e, t);
		return r.second - r.first;
	}

	int select(int a, T t) {
		pii r = search(0, data.size(), t);
		return  backward(r.first + a - 1, t);
	}

	T kthelement(int s, int e, int k, int b = 0) {
		int eo = bitv[b].rank(e, 0), so = bitv[b].rank(s, 0), cou = eo - so;
		if (b == bitsize - 1) return cou <= k;
		return (cou <= k ?
			kthelement(border[b + 1] + (s - so), border[b + 1] + (s - so) + (e - s - cou), k - cou, b + 1) :
			kthelement(so, so + cou, k, b + 1)) | ((cou <= k) << (bitsize - b - 1));
	}
	inline int lessthan(int s, int e, T t) {
		int ans = 0, ns, ne;
		int i = 0;
		int eo = bitv[i].rank(e, 0), so = bitv[i].rank(s, 0), cou = (eo - so);
		if (bitcheck(t, bitsize - i - 1)) {
			ns = border[i + 1] + (s - so);
			ne = border[i + 1] + (s - so) + (e - s - cou);
			s = ns, e = ne;
			ans += cou;
		}
		else {
			s = so;
			e = so + cou;
		}
		i++;

		eo = bitv[i].rank(e, 0), so = bitv[i].rank(s, 0), cou = (eo - so);
		if (bitcheck(t, bitsize - i - 1)) {
			ns = border[i + 1] + (s - so);
			ne = border[i + 1] + (s - so) + (e - s - cou);
			s = ns, e = ne;
			ans += cou;
		}
		else {
			s = so;
			e = so + cou;
		}
		i++;
		eo = bitv[i].rank(e, 0), so = bitv[i].rank(s, 0), cou = (eo - so);
		if (bitcheck(t, bitsize - i - 1)) {
			ns = border[i + 1] + (s - so);
			ne = border[i + 1] + (s - so) + (e - s - cou);
			s = ns, e = ne;
			ans += cou;
		}
		else {
			s = so;
			e = so + cou;
		}
		i++;
		eo = bitv[i].rank(e, 0), so = bitv[i].rank(s, 0), cou = (eo - so);
		if (bitcheck(t, bitsize - i - 1)) {
			ns = border[i + 1] + (s - so);
			ne = border[i + 1] + (s - so) + (e - s - cou);
			s = ns, e = ne;
			ans += cou;
		}
		else {
			s = so;
			e = so + cou;
		}
		i++;
		eo = bitv[i].rank(e, 0), so = bitv[i].rank(s, 0), cou = (eo - so);
		if (bitcheck(t, bitsize - i - 1)) {
			ns = border[i + 1] + (s - so);
			ne = border[i + 1] + (s - so) + (e - s - cou);
			s = ns, e = ne;
			ans += cou;
		}
		else {
			s = so;
			e = so + cou;
		}
		i++;
		eo = bitv[i].rank(e, 0), so = bitv[i].rank(s, 0), cou = (eo - so);
		if (bitcheck(t, bitsize - i - 1)) {
			ns = border[i + 1] + (s - so);
			ne = border[i + 1] + (s - so) + (e - s - cou);
			s = ns, e = ne;
			ans += cou;
		}
		else {
			s = so;
			e = so + cou;
		}
		i++;
		eo = bitv[i].rank(e, 0), so = bitv[i].rank(s, 0), cou = (eo - so);
		if (bitcheck(t, bitsize - i - 1)) {
			ns = border[i + 1] + (s - so);
			ne = border[i + 1] + (s - so) + (e - s - cou);
			s = ns, e = ne;
			ans += cou;
		}
		else {
			s = so;
			e = so + cou;
		}
		i++;
		eo = bitv[i].rank(e, 0), so = bitv[i].rank(s, 0), cou = (eo - so);
		if (bitcheck(t, bitsize - i - 1)) {
			ns = border[i + 1] + (s - so);
			ne = border[i + 1] + (s - so) + (e - s - cou);
			s = ns, e = ne;
			ans += cou;
		}
		else {
			s = so;
			e = so + cou;
		}
		i++;
		eo = bitv[i].rank(e, 0), so = bitv[i].rank(s, 0), cou = (eo - so);
		if (bitcheck(t, bitsize - i - 1)) {
			ns = border[i + 1] + (s - so);
			ne = border[i + 1] + (s - so) + (e - s - cou);
			s = ns, e = ne;
			ans += cou;
		}
		else {
			s = so;
			e = so + cou;
		}
		i++;
		eo = bitv[i].rank(e, 0), so = bitv[i].rank(s, 0), cou = (eo - so);
		if (bitcheck(t, bitsize - i - 1)) {
			ns = border[i + 1] + (s - so);
			ne = border[i + 1] + (s - so) + (e - s - cou);
			s = ns, e = ne;
			ans += cou;
		}
		else {
			s = so;
			e = so + cou;
		}
		i++;
		eo = bitv[i].rank(e, 0), so = bitv[i].rank(s, 0), cou = (eo - so);
		if (bitcheck(t, bitsize - i - 1)) {
			ns = border[i + 1] + (s - so);
			ne = border[i + 1] + (s - so) + (e - s - cou);
			s = ns, e = ne;
			ans += cou;
		}
		else {
			s = so;
			e = so + cou;
		}
		i++;
		eo = bitv[i].rank(e, 0), so = bitv[i].rank(s, 0), cou = (eo - so);
		if (bitcheck(t, bitsize - i - 1)) {
			ns = border[i + 1] + (s - so);
			ne = border[i + 1] + (s - so) + (e - s - cou);
			s = ns, e = ne;
			ans += cou;
		}
		else {
			s = so;
			e = so + cou;
		}
		i++;
		eo = bitv[i].rank(e, 0), so = bitv[i].rank(s, 0), cou = (eo - so);
		if (bitcheck(t, bitsize - i - 1)) {
			ns = border[i + 1] + (s - so);
			ne = border[i + 1] + (s - so) + (e - s - cou);
			s = ns, e = ne;
			ans += cou;
		}
		else {
			s = so;
			e = so + cou;
		}
		i++;
		eo = bitv[i].rank(e, 0), so = bitv[i].rank(s, 0), cou = (eo - so);
		if (bitcheck(t, bitsize - i - 1)) {
			ns = border[i + 1] + (s - so);
			ne = border[i + 1] + (s - so) + (e - s - cou);
			s = ns, e = ne;
			ans += cou;
		}
		else {
			s = so;
			e = so + cou;
		}
		i++;
		eo = bitv[i].rank(e, 0), so = bitv[i].rank(s, 0), cou = (eo - so);
		if (bitcheck(t, bitsize - i - 1)) {
			ns = border[i + 1] + (s - so);
			ne = border[i + 1] + (s - so) + (e - s - cou);
			s = ns, e = ne;
			ans += cou;
		}
		else {
			s = so;
			e = so + cou;
		}
		i++;
		eo = bitv[i].rank(e, 0), so = bitv[i].rank(s, 0), cou = (eo - so);
		if (bitcheck(t, bitsize - i - 1)) {
			ns = border[i + 1] + (s - so);
			ne = border[i + 1] + (s - so) + (e - s - cou);
			s = ns, e = ne;
			ans += cou;
		}
		else {
			s = so;
			e = so + cou;
		}
		i++;
		eo = bitv[i].rank(e, 0), so = bitv[i].rank(s, 0), cou = (eo - so);
		if (bitcheck(t, bitsize - i - 1)) {
			ns = border[i + 1] + (s - so);
			ne = border[i + 1] + (s - so) + (e - s - cou);
			s = ns, e = ne;
			ans += cou;
		}
		else {
			s = so;
			e = so + cou;
		}
		i++;
		eo = bitv[i].rank(e, 0), so = bitv[i].rank(s, 0), cou = (eo - so);
		if (bitcheck(t, bitsize - i - 1)) {
			ns = border[i + 1] + (s - so);
			ne = border[i + 1] + (s - so) + (e - s - cou);
			s = ns, e = ne;
			ans += cou;
		}
		else {
			s = so;
			e = so + cou;
		}
		i++;
		eo = bitv[i].rank(e, 0), so = bitv[i].rank(s, 0), cou = (eo - so);
		if (bitcheck(t, bitsize - i - 1)) {
			ns = border[i + 1] + (s - so);
			ne = border[i + 1] + (s - so) + (e - s - cou);
			s = ns, e = ne;
			ans += cou;
		}
		else {
			s = so;
			e = so + cou;
		}
		i++;
		eo = bitv[i].rank(e, 0), so = bitv[i].rank(s, 0), cou = (eo - so);
		if (bitcheck(t, bitsize - i - 1)) {
			ns = border[i + 1] + (s - so);
			ne = border[i + 1] + (s - so) + (e - s - cou);
			s = ns, e = ne;
			ans += cou;
		}
		else {
			s = so;
			e = so + cou;
		}
		i++;
		eo = bitv[i].rank(e, 0), so = bitv[i].rank(s, 0), cou = (eo - so);
		if (bitcheck(t, bitsize - i - 1)) {
			ns = border[i + 1] + (s - so);
			ne = border[i + 1] + (s - so) + (e - s - cou);
			s = ns, e = ne;
			ans += cou;
		}
		else {
			s = so;
			e = so + cou;
		}
		i++;
		eo = bitv[i].rank(e, 0), so = bitv[i].rank(s, 0), cou = (eo - so);
		if (bitcheck(t, bitsize - i - 1)) {
			ns = border[i + 1] + (s - so);
			ne = border[i + 1] + (s - so) + (e - s - cou);
			s = ns, e = ne;
			ans += cou;
		}
		else {
			s = so;
			e = so + cou;
		}
		i++;
		eo = bitv[i].rank(e, 0), so = bitv[i].rank(s, 0), cou = (eo - so);
		if (bitcheck(t, bitsize - i - 1)) {
			ns = border[i + 1] + (s - so);
			ne = border[i + 1] + (s - so) + (e - s - cou);
			s = ns, e = ne;
			ans += cou;
		}
		else {
			s = so;
			e = so + cou;
		}
		i++;
		eo = bitv[i].rank(e, 0), so = bitv[i].rank(s, 0), cou = (eo - so);
		if (bitcheck(t, bitsize - i - 1)) {
			ns = border[i + 1] + (s - so);
			ne = border[i + 1] + (s - so) + (e - s - cou);
			s = ns, e = ne;
			ans += cou;
		}
		else {
			s = so;
			e = so + cou;
		}
		i++;
		eo = bitv[i].rank(e, 0), so = bitv[i].rank(s, 0), cou = (eo - so);
		if (bitcheck(t, bitsize - i - 1)) {
			ns = border[i + 1] + (s - so);
			ne = border[i + 1] + (s - so) + (e - s - cou);
			s = ns, e = ne;
			ans += cou;
		}
		else {
			s = so;
			e = so + cou;
		}
		i++;
		eo = bitv[i].rank(e, 0), so = bitv[i].rank(s, 0), cou = (eo - so);
		if (bitcheck(t, bitsize - i - 1)) {
			ns = border[i + 1] + (s - so);
			ne = border[i + 1] + (s - so) + (e - s - cou);
			s = ns, e = ne;
			ans += cou;
		}
		else {
			s = so;
			e = so + cou;
		}
		i++;
		eo = bitv[i].rank(e, 0), so = bitv[i].rank(s, 0), cou = (eo - so);
		if (bitcheck(t, bitsize - i - 1)) {
			ns = border[i + 1] + (s - so);
			ne = border[i + 1] + (s - so) + (e - s - cou);
			s = ns, e = ne;
			ans += cou;
		}
		else {
			s = so;
			e = so + cou;
		}
		i++;
		eo = bitv[i].rank(e, 0), so = bitv[i].rank(s, 0), cou = (eo - so);
		if (bitcheck(t, bitsize - i - 1)) {
			ns = border[i + 1] + (s - so);
			ne = border[i + 1] + (s - so) + (e - s - cou);
			s = ns, e = ne;
			ans += cou;
		}
		else {
			s = so;
			e = so + cou;
		}
		i++;
		eo = bitv[i].rank(e, 0), so = bitv[i].rank(s, 0), cou = (eo - so);
		if (bitcheck(t, bitsize - i - 1)) {
			ns = border[i + 1] + (s - so);
			ne = border[i + 1] + (s - so) + (e - s - cou);
			s = ns, e = ne;
			ans += cou;
		}
		else {
			s = so;
			e = so + cou;
		}
		i++;
		eo = bitv[i].rank(e, 0), so = bitv[i].rank(s, 0), cou = (eo - so);
		if (bitcheck(t, bitsize - i - 1)) {
			ns = border[i + 1] + (s - so);
			ne = border[i + 1] + (s - so) + (e - s - cou);
			s = ns, e = ne;
			ans += cou;
		}
		else {
			s = so;
			e = so + cou;
		}
		i++;
		eo = bitv[i].rank(e, 0), so = bitv[i].rank(s, 0), cou = (eo - so);
		if (bitcheck(t, bitsize - i - 1)) {
			ns = border[i + 1] + (s - so);
			ne = border[i + 1] + (s - so) + (e - s - cou);
			s = ns, e = ne;
			ans += cou;
		}
		else {
			s = so;
			e = so + cou;
		}
		i++;
		eo = bitv[i].rank(e, 0), so = bitv[i].rank(s, 0), cou = (eo - so);
		if (bitcheck(t, bitsize - i - 1)) {
			ns = border[i + 1] + (s - so);
			ne = border[i + 1] + (s - so) + (e - s - cou);
			s = ns, e = ne;
			ans += cou;
		}
		else {
			s = so;
			e = so + cou;
		}
		i++;

		return e - s + ans;
	}

	void clear() {
		REP(i, bitsize) bitv[i].clear();
	}
};

class Heavy_Light_Decomposition {
public:
	BiDGraph g, compg;
	vector<int> sz, depth, hd, chain, par;

	int bn = 0;
	vector<int> bvn, inbn;
	vector<vector<int>> bv;

	Heavy_Light_Decomposition(BiDGraph graph, int root) :
		g(graph), compg(graph.vn), sz(graph.vn, 1), hd(graph.vn), depth(graph.vn), chain(graph.vn), par(graph.vn),
		bvn(graph.vn), inbn(graph.vn) {
		getsz(root, root);
		bv.push_back(vector<int>());
		HLD(root, -1, root, 0);
	}

	int getsz(int cur, int p) {
		par[cur] = p;
		for (auto itr : g.g[cur])
			if (p != itr.first)
				depth[itr.first] = depth[cur] + 1, sz[cur] += getsz(itr.first, cur), hd[cur] = max(hd[itr.first] + 1, hd[cur]);
		return sz[cur];
	}

	void HLD(int cur, int p, int head, int num) {
		chain[cur] = head, bvn[cur] = num;
		inbn[cur] = bv[num].size(), bv[num].push_back(cur);
		pii Maxc = { -1,-1 };
		for (auto itr : g.g[cur])
			if (itr.first != p)
				if (Maxc.first< sz[itr.first])
					Maxc = max(Maxc, { sz[itr.first], itr.first });


		for (auto itr : g.g[cur])
			if (itr.first != p) {
				int nb = num;
				if (itr.first != Maxc.second) {
					bv.push_back(vector<int>());
					nb = ++bn;
				}
				HLD(itr.first, cur, itr.first == Maxc.second ? head : itr.first, nb);
			}
	}

	int lca(int a, int b) {
		if (chain[a] == chain[b]) return depth[a] < depth[b] ? a : b;
		if (depth[chain[a]] > depth[chain[b]])
			return lca(par[chain[a]], b);
		return lca(a, par[chain[b]]);
	}

	void for_each_edge(int a, int b, function<void(int, int)> func) {
		if (chain[a] == chain[b]) return func(inbn[a] < inbn[b] ? a : b, inbn[a] < inbn[b] ? b : a);
		if (depth[chain[a]] < depth[chain[b]]) swap(a, b);
		for_each_edge(a, chain[a], func), for_each_edge(par[chain[a]], b, func);
	}
};
signed main() {
	int n, q;
	scnaf("%d %d", &n, &q);
	vector<int> num(n);
	REP(i, n)
		scanf("%d", &num[i]);

	BiDGraph g(n);
	g.scan(n - 1, 1, 0);
	srand(time(0));
	Heavy_Light_Decomposition hld(g, rand()%n);
	vector<WaveletMatrix<int>> wm;
	wm.reserve(n);
	REP(i, hld.bv.size()) {
		vector<int> buf(hld.bv[i].size());
		REP(j, hld.bv[i].size()) {
			buf[hld.inbn[hld.bv[i][j]]] = num[hld.bv[i][j]];
		}
		wm.push_back(WaveletMatrix<int>(buf));
	}

	REP(i, q) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		a--, b--;
		vector<pii> ku;
		int M = -1;
		hld.for_each_edge(a, b, [&](int v, int w) {
			M = max(M, wm[hld.bvn[v]].Max);
			ku.push_back({ v,w });
		});
		int l = 0, r = M + 1;
		while (r - l > 1) {
			int cou = 0;
			int mid = (l + r) / 2;
			for (auto itr : ku)
				cou += wm[hld.bvn[itr.first]].lessthan(hld.inbn[itr.first], hld.inbn[itr.second] + 1, mid);

			if (cou < c)l = mid;
			else r = mid;
		}

		printf("%d\n", l + 1);

	}
	return 0;
}

Compiler output:
a.cc:106:18: error: expected ';' at end of member declaration
  106 |         unsigned __int8* blockrank;
      |                  ^~~~~~
      |                        ;
a.cc:106:26: error: ISO C++ forbids declaration of 'blockrank' with no type [-fpermissive]
  106 |         unsigned __int8* blockrank;
      |                          ^~~~~~~~~
a.cc: In constructor 'Bitvector::Bitvector(int)':
a.cc:111:30: error: expected primary-expression before 'unsigned'
  111 |                 blockrank = (unsigned __int8*)calloc((n + 7) / 8 + 1, sizeof(__int8));
      |                              ^~~~~~~~
a.cc:111:30: error: expected ')' before 'unsigned'
a.cc:111:29: note: to match this '('
  111 |                 blockrank = (unsigned __int8*)calloc((n + 7) / 8 + 1, sizeof(__int8));
      |                             ^