求条玄小号关

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

using i128 = __int128;
using u128 = unsigned __int128;

mt19937_64 mrand((u64)random_device{}() << 32 ^ random_device{}() ^
	chrono::high_resolution_clock::now().time_since_epoch().count());
template<class T = i64,class T2>T rnd(T l,T2 r){
return uniform_int_distribution<T>(l,r)(mrand);}

void solve(){
	int n;
	cin >> n;

	vector<vector<int>> a(n + 1);
	vector<int> c(n + 1);

	for (int i = 1;i <= n;i++)
		cin >> c[i];

	for (int i = n;--i;){
		int x,y;
		cin >> x >> y;

		a[x].push_back(y);
		a[y].push_back(x);
	}

	vector<int> sz(n + 1),d(n + 1),f(n + 1),at(n + 1),to(n + 1),hson(n + 1);

	auto dfs = [&](auto &&self,int x,int y) -> void {
		sz[x] = 1;
		f[x] = y;

		for (auto i:a[x]) if (i != y){
			self(self,i,x);
			sz[x] += sz[i];

			if (sz[i] > sz[hson[x]])
				hson[x] = i;
		}
	};

	dfs(dfs,1,0);

	int top = 0;
	vector<int> dfn(1);
	dfn.reserve(n + 1);

	auto dfs2 = [&](auto &&self,int x,int y) -> void {
		if (!to[x]) to[x] = x;
		at[x] = ++top;
		dfn.push_back(x);

		if (!hson[x]) return ;

		to[hson[x]] = to[x];
		self(self,hson[x],x);

		for (auto i:a[x]) if (i != y&&i != hson[x])
			self(self,i,x);
	};

	dfs2(dfs2,1,0);

	vector<vector<int>> st(__lg(n) + 1,vector<int>(n + 1));

	for (int i = 1;i <= n;i++)
		st[0][i] = c[dfn[i]];

	for (int i = 1;1 << i <= n;i++)
		for (int j = 1;j + (1 << i) - 1 <= n;j++)
			st[i][j] = st[i - 1][j] | st[i - 1][j + (1 << i - 1)];

	auto query = [&](int l,int r){
		if (l > r) swap(l,r);
		int lg = __lg(r - l + 1);
		return st[lg][l] | st[lg][r - (1 << lg) + 1];
	};

	auto q_lca = [&](int x,int y){
		for (;to[x] != to[y];){
			if (d[to[x]] < d[to[y]]) swap(x,y);
			x = f[to[x]];
		}

		return d[x] < d[y]?x:y;
	};

	auto skip = [&](int x,int pvt){
		int v = 0;

		for (;__builtin_popcount(v | query(at[to[x]],at[x])) < pvt;x = f[to[x]]);

		int l = at[to[x]],r = at[x] + 1;

		for (;l + 1 < r;){
			int mid = l + r >> 1;

			if (__builtin_popcount(v | query(mid,at[x])) >= pvt)
				l = pvt;
			else
				r = pvt;
		}

		return dfn[l];
	};

	auto skip_d = [&](int x,int td){
		for (;d[to[x]] > td;x = f[to[x]]);
		return dfn[at[to[x]] + td - d[to[x]]];
	};

	auto q_val = [&](int x,int y){
		int v = 0;

		for (;to[x] != to[y];){
			if (d[to[x]] < d[to[y]]) swap(x,y);
			v |= query(at[to[x]],at[x]);
			x = f[to[x]];
		}

		return v | query(at[x],at[y]);
	};

	auto q_path = [&](int s,int l,int t){
		int v = q_val(s,l),ans = 0;

		for (int i = 1;i <= __builtin_popcount(v);i++)
			ans = max(ans,i + q_val(f[(skip(s,i) == l?skip_d(t,d[l] + 1):skip(s,i))],t));

		return ans;
	};

	int q;
	cin >> q;

	for (;q--;){
		int x,y;
		cin >> x >> y;

		int lca = q_lca(x,y);

		cout << max(q_path(x,lca,y),q_path(y,lca,x)) << ' ';
	}

	cout << '\n';
}

int main (){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);

	int T;
	cin >> T;

	for (;T--;solve());
}