P9745 "KDOI-06-S" XOR on Tree

Given a tree with $n$ nodes, the $i$-th node has a node weight $x_i$. For the $n-1$ edges on the tree, each edge can be chosen to be deleted or kept, so there are $2^{n-1}$ ways to decide whether to delete each edge. For each edge-deletion plan, suppose the resulting graph has $k$ connected components. Define the value of this plan as the product of the XOR sums of node weights within each connected component. Formally, if the graph contains connected components $C_1,C_2,\ldots,C_k$, where $C_i$ is the vertex set of the $i$-th connected component, let $v_i=\bigoplus_{u\in C_i} x_u$, then the value of this plan is $v_1\times v_2\times \cdots\times v_k$. Find the sum of the **values** over all these $2^{n-1}$ edge-deletion plans, and output the answer modulo $998~244~353$.

Read input from standard input. The first line contains a positive integer $n$, denoting the number of nodes in the tree. The second line contains $n$ non-negative integers $x_1,x_2,\ldots,x_n$, denoting the node weight of each node. The third line contains $n-1$ positive integers $f_2,f_3,\ldots,f_n$, indicating that there is an undirected edge between node $i$ and $f_{i}$.

Write output to standard output. Output one line containing one integer, denoting the sum of the **values** over all $2^{n-1}$ edge-deletion plans, modulo $998~244~353$.

**[Sample Explanation #1]** There are four edge-deletion plans: * Delete no edges: the graph has exactly one connected component, and the value is $1\oplus2\oplus3=0$. * Delete edge $(1,2)$: the graph has two connected components, and the value is $(1\oplus3)\times2=4$. * Delete edge $(1,3)$: the graph has two connected components, and the value is $(1\oplus2)\times3=9$. * Delete edges $(1,2)$ and $(1,3)$: the graph has three connected components, and the value is $1\times2\times3=6$. The total sum of values is $0+4+9+6=19$. **[Sample #3]** See `xor/xor3.in` and `xor/xor3.ans` in the contestant directory. This sample satisfies the constraints for test points $6\sim7$. **[Sample #4]** See `xor/xor4.in` and `xor/xor4.ans` in the contestant directory. This sample satisfies the constraints for test point $8$. **[Sample #5]** See `xor/xor5.in` and `xor/xor5.ans` in the contestant directory. This sample satisfies the constraints for test point $9$. **[Sample #6]** See `xor/xor6.in` and `xor/xor6.ans` in the contestant directory. This sample satisfies the constraints for test points $19\sim21$. *** **[Constraints]** For all data, it is guaranteed that: $1\leq n\leq5\times10^5$, $0\leq x_i\leq10^{18}$, $1\leq f_i