P14509 树上求值 tree

对于两个权值序列 $A(0)_0,A(0)_1,\dots,A(0)_{20}$ 与 $A(1)_0,A(1)_1,\dots,A(1)_{20}$，记 $x=\sum_{i=0}^{20} b_i2^{i}$，其中 $b_i\in \{0,1\}$，定义 $f(x)=\prod_{i=0}^{20} A(b_i)_i$。 给定一颗树。有 $T$ 组数据，每组数据给定树的根结点编号 $r_i$，模数 $m$ 与权值序列 $A(0),A(1)$，你需要对每组数据都求出答案。 对于一颗根为 $r_i$ 的有根树，每个结点 $x$ 的深度 $d_x$ 定义为 $x$ 到 $r_i$ 的简单路径上的**结点数量**。记 $\operatorname{LCA*}(x,y)$ 为结点 $x,y$ 最近公共祖先的编号。对于每个树上的结点 $x$，你需要求出 $s_x=\sum_{i=1}^n f(i+d_{\operatorname{LCA*}(i,x)})$ 对 $m$ 取模后的结果。

**本题包含多组测试数据。** 输入的第一行包含一个整数 $n$。 接下来 $n-1$ 行，每行两个整数 $u_i,v_i$ 表示树上一条连接结点 $u_i$ 与 $v_i$ 的边。 接下来一行一个整数 $T$，表示数据的组数。 接下来共 $3T$ 行。对于每组数据输入三行： - 第一行包含两个整数 $r_i,m$。 - 第二行包含 $21$ 个整数 $A(0)_0,A(0)_1,\dots,A(0)_{20}$。 - 第三行包含 $21$ 个整数 $A(1)_0,A(1)_1,\dots,A(1)_{20}$。

共输出 $T$ 行。对于每组数据，记 $s_x$ 表示结点 $x$ 的答案，你只需要输出一行包含一个整数，表示 $(1\times s_1) \oplus (2\times s_2) \oplus \dots \oplus (n\times s_n)$ 的结果。

**【样例 1 解释】** 对于第一组数据，所有点的答案都是 $5$。于是 $(1\times s_1) \oplus (2\times s_2) \oplus \dots \oplus (n\times s_n)=(1\times 5) \oplus (2\times 5) \oplus (3\times 5) \oplus (4\times 5) \oplus (5\times 5)=13$。 对于第二组数据，$(s_1,s_2,s_3,s_4,s_5)=(9,7,8,6,8)$。 **【样例 2】** 见附件的 tree/tree2.in 与 tree/tree2.ans。 该样例满足测试点 $1\sim 2$ 的约束条件。 **【样例 3】** 见附件的 tree/tree3.in 与 tree/tree3.ans。 该样例满足测试点 $6$ 的约束条件。 **【样例 4】** 见附件的 tree/tree4.in 与 tree/tree4.ans。 该样例满足测试点 $7\sim 10$ 的约束条件。 **【样例 5】** 见附件的 tree/tree5.in 与 tree/tree5.ans。 该样例满足测试点 $17\sim 20$ 的约束条件。 **【数据范围】** 对于所有测试数据，保证 $1\le T\le 10$，$1\le r_i\le n\le 2\times 10^5$，$0\le A(0)_i,A(1)_i