「KDOI-06-S」树上异或

给定一棵包含 $n$ 个节点的树，第 $i$ 个点有一个点权 $x_i$。 对于树上的 $n-1$ 条边，每条边选择删除或不删除，有 $2^{n-1}$ 种选择是否删除每条边的方案。 对于每种删除边的方案，设删除后的图包含 $k$ 个连通块，定义这个方案的权值为图中连通块点权异或和的乘积。形式化地说，若这张图包含连通块 $C_1,C_2,\ldots,C_k$，其中 $C_i$ 是第 $i$ 个连通块的顶点集合，设 $v_i=\bigoplus_{u\in C_i} x_u$，则这个方案的权值为 $v_1\times v_2\times \cdots\times v_k$。 求这 $2^{n-1}$ 种删除边的方案的**权值**之和，答案对 $998~244~353$ 取模。 ## Input 从标准输入读入数据。 输入的第一行包含一个正整数 $n$，表示树的节点个数。 第二行 $n$ 个非负整数 $x_1,x_2,\ldots,x_n$，表示每个点的点权。 第三行 $n-1$ 个正整数 $f_2,f_3,\ldots,f_n$，表示节点 $i$ 与 $f_{i}$ 之间有一条无向边。 ## Output 输出到标准输出。 输出包含一行一个整数，表示所有 $2^{n-1}$ 种删除边的方案的**权值**之和，答案对 $998~244~353$ 取模。 [samples] ## Note **【样例解释 #1】** 有四种删除边的方案： * 不删除边：图有且仅有一个连通块，权值为 $1\oplus2\oplus3=0$。 * 删除 $(1,2)$ 一条边：图包含两个连通块，权值为 $(1\oplus3)\times2=4$。 * 删除 $(1,3)$ 一条边：图包含两个连通块，权值为 $(1\oplus2)\times3=9$。 * 删除 $(1,2)$，$(1,3)$ 两条边：图包含三个连通块，权值为 $1\times2\times3=6$。 所有方案权值的总和为 $0+4+9+6=19$。 **【样例 #3】** 见选手目录下的 `xor/xor3.in` 与 `xor/xor3.ans`。 这个样例满足测试点 $6\sim7$ 的条件限制。 **【样例 #4】** 见选手目录下的 `xor/xor4.in` 与 `xor/xor4.ans`。 这个样例满足测试点 $8$ 的条件限制。 **【样例 #5】** 见选手目录下的 `xor/xor5.in` 与 `xor/xor5.ans`。 这个样例满足测试点 $9$ 的条件限制。 **【样例 #6】** 见选手目录下的 `xor/xor6.in` 与 `xor/xor6.ans`。 这个样例满足测试点 $19\sim21$ 的条件限制。 *** **【数据范围】** 对于所有数据保证：$1\leq n\leq5\times10^5$，$0\leq x_i\leq10^{18}$，$1\leq f_i<i$。 | 测试点编号 | $n\leq$ | $x_i$ | 特殊性质 | |:--:|:--:|:--:|:--:| | $1\sim2$ | $12$ | $\leq10^9$ | 无 | | $3$ | $2000$ | $=1$ | 无 | | $4$ | $10^5$ | $=1$ | A | | $5$ | $10^5$ | $=1$ | B | | $6\sim7$ | $10^5$ | $=1$ | 无 | | $8$ | $10^5$ | $\leq7$ | A | | $9$ | $10^5$ | $\leq7$ | B | | $10\sim11$ | $10^5$ | $\leq7$ | 无 | | $12\sim16$ | $200$ | $\leq8191$ | 无 | | $17$ | $10^5$ | $\leq10^9$ | A | | $18$ | $10^5$ | $\leq10^9$ | B | | $19\sim21$ | $10^5$ | $\leq10^9$ | 无 | | $22\sim25$ | $5\times10^5$ | $\leq10^{18}$ | 无 | * 特殊性质 A：保证对于任意 $1< i\le n$，$f_i=i-1$。 * 特殊性质 B：保证对于任意 $1< i\le n$，$f_i=1$。 *** **【提示】** $\oplus$ 表示按位异或运算。 本题输入输出量较大，请使用适当的 I/O 方式。 **请注意常数因子对程序运行效率产生的影响。**