P9745 「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$ 取模。

无

无

**【样例解释 #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