BOJ 18263 Milk Visits

int n,m,c[1 << 17];
int Top[1 << 17], Par[1 << 17], Dep[1 << 17], sz[1 << 17], in[1 << 17],out[1 << 17];
vector<int> Inp[1 << 17], G[1 << 17];
 
struct MST{
	int sz = 1 << 17;
	vi T[1 << 18];
 
	inline void insert(int x, int v){
		x |= sz; T[x].pb(v);
	}
 
	void build(){
		for(int i = sz - 1; i; i--){
			T[i].resize(si(T[i << 1]) + si(T[i << 1 | 1]));
			merge(all(T[i << 1]), all(T[i << 1 | 1]), T[i].begin());
		}
	}
 
	int query(int l, int r, int x){
		int ret = 0;
		l |= sz; r |= sz;
		while(l <= r){
			if(l & 1) ret += upper_bound(all(T[l]), x) - lower_bound(all(T[l]), x), l++;
			if(~r & 1) ret += upper_bound(all(T[r]), x) - lower_bound(all(T[r]), x), r--;
			l >>= 1, r >>= 1;
		}
		return ret;
	}
};
 
void add_edge(int a, int b){
	Inp[a].pb(b); Inp[b].pb(a);
}
 
void dfs0(int cur, int par = -1){
	for(auto& nxt : Inp[cur]) if(nxt != par)
		Dep[nxt] = Dep[cur] + 1, Par[nxt] = cur, G[cur].pb(nxt),dfs0(nxt, cur);
}
 
void dfs1(int cur){
	sz[cur] = 1;
	for(auto& nxt : G[cur]){
		dfs1(nxt); sz[cur] += sz[nxt];
		if(sz[nxt] > sz[G[cur][0]]) swap(nxt, G[cur][0]);
	}
}
 
void dfs2(int cur){
	static int temp = 0; in[cur] = ++temp;
	for(auto& nxt : G[cur]) Top[nxt] = nxt == G[cur][0] ? Top[cur] : nxt, dfs2(nxt);
	out[cur] = temp;
}
 
void solve(){
	ri(n, m);
	for(int i = 1; i <= n; i++) ri(c[i]);
	for(int i = 1; i < n; i++){
		int a,b; ri(a, b);
		add_edge(a, b);
	}
	dfs0(1); dfs1(1); dfs2(Top[1] = 1);
	MST mst;
	for(int i = 1; i <= n; i++) mst.insert(in[i], c[i]);
	mst.build();
	for(int i = 0; i < m; i++){
		int a,b,c; ri(a, b, c);
		int res = 0;
		for(; Top[a] != Top[b]; a = Par[Top[a]]){
			if(Dep[Top[a]] < Dep[Top[b]]) swap(a, b);
			res += mst.query(in[Top[a]], in[a], c);
		}
		if(in[a] > in[b]) swap(a, b);
		res += mst.query(in[a], in[b], c);
		cout << (res ? 1 : 0);
	}
}