9269 - 树上异或

给定一棵树包含n个节点的树，以及每个节点的权值a_i，对于树上的n-1条边，每条边可以选择删除或不删除，有2^(n-1)种选择方案。 现在需要去验证每一种删除边的方案，假设删除一边后有x个连通块，当前删除方案的权值为所有连通块点权异或(xor)和的乘积。若删除一条边后图中包含有C1,C2,…,Ci个连通块，其中C_i为第i个连通块顶点的集合，则此删除方案的权值v为v1×v2×…×vi。
求2^(n-1)种删除方案的权值之和，答案对998244353取模。

第一行一个正整数n，表示树的节点个数。
第二行一行n 个正整数，表示每个节点的权值。
第三行一行n-1 个正整数b2,b3,…,bn，表示节点i与节点b_i之间有一条边。

输出一行一个整数，表示所有2^(n-1)种删除方案权值之和对998244353取模的结果。

【样例1解释】
根据第三行输入信息可知，节点2与节点1有一条边，节点3与节点1有一条边，可得树的结构为：

3条边有2^(3-1)种删除方案，分别为：
（1） 不删除：有且仅有一个连通块，权值为1 xor 2 xor 3=0。
（2） 删除(1,3)一条边：含有两个连通块，权值为(1 xor 2)×3=9。
（3） 删除(1,2)一条边：含有两个连通块，权值为(1 xor 3)×2=4。
（4） 删除(1,2)，(1,3)两条边：含有3个连通块，权值为1×2×3=6。
所有删除方案的权值之和为0+4+9+6=19。
【样例2解释】
根据第三行输入信息可知节点2与节点1有一条边，节点3与节点1有一条边，节点4与节点2有一条边，节点5与节点2有一条边，可得树的结构为：
5条边有2^(5-1)=16种删除方案，分别为：
（1）不删除，有且仅有一个连通块，权值为3 xor 4 xor 5 xor 6 xor 7=3。
（2）删除(1,2)一条边，含两个连通块权值为(3 xor 5)×(4 xor 6 xor 7)=6×5=30。
……
【数据范围】
对于100%的数据1≤n≤10^5，1≤a_i≤10^18

云南编程挑战赛