树上最大值

发布时间: 2018年6月14日 17:53   最后更新: 2018年6月14日 17:58   时间限制: 5000ms   内存限制: 512M

给定一个连通无向图$G=(V,E)$,共有$n$个点,$n-1$条边,每个点有一个权值$a_i$。

CSL想知道:对于树上的两个点$u,v$,它们的路径上的点哪一个与$x$异或值最大。

第一行有一个整数$T$,表示测试数据的组数。
对于每组测试数据,输入两个整数$n,q$,表示点的个数和询问个数。
接下来一行,输入$n$个数,$a_1,a_2 \ldots a_n$,表示每个点的点权。
接下来$n - 1$行,每行两个数$u,v$,表示$u$和$v$之间有一条边。
接下来$q$行,每行三个数$u,v,x$,表示CSL的一次询问。
$T \leq 5$
$2 \le n,q \le 10 ^ {5}$
$0 \le a_i \le 10 ^ {9}, 1 \le i \le n$
$1 \le u,v \le n, 0 \le x \le 10 ^{9}$

对于每组测试数据,每个询问输出一行答案。

复制
1
6 6
1 1 4 5 1 4
1 2
1 3
2 4
4 5
4 6
2 3 4
5 3 4
3 2 1
3 5 0
5 2 4
2 6 1
1
1
4
5
1
4

data structure

ACM集训队暑期集训热身赛