异或树

题号：NC22527
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

有一棵n个节点的异或树，1号点为根，每个节点有一个权值 $w_i$ 。每次询问给出u,x，询问子树u内，点的权值大于x的所有权值异或x的和。即

$\sum_\limits{v是u子树中的点,\ w[v]>x}x \oplus w[v]$

由于这是一棵异或树，所以，如果一个数出现了两次，那么这两个点的权值就消失了（点并没有消失，即树的形态没有发生变化，只是在计算时忽略这两个点的权值。）消失过程发生在一次询问时，如果子树内两个点的权值一样，那么这两个点的权值同时消失，直到无法再有点对消失后查询。

第一行两个整数n，Q，分别表示点的个数和询问个数。
第二行n个整数。
第二行到第n行，每行两个整数，描述一条边u,v。
接下来q行，每行两个整数u,x，描述一次询问。

对于每次询问，输出一个整数表示答案。

示例1

复制

6 5
2 3 4 2 3 3
1 2
2 3
2 4
2 5
1 6
1 1
1 4
2 1
2 3
6 1

复制