33OJ
登录 注册

#P17781. 千早爱音不是罪过

千早爱音不是罪过

背景

『即使失败一次,也得相信自己还能重新开始;不然人生这么长,会撑不住哦。』

『 一起在迷失之中前进吧!』

题目描述

爱音喜欢「描绘未来」。

她将未来的事件想象成了一棵带点权有根树,事件 11 为根,事件 ii 的权值为 aia_i。

爱音想要给每个事件确定一个发生顺序,具体地,事件 11 的发生顺序必须为 11,其余事件的发生顺序应大于其父亲的发生顺序,所有事件的发生顺序互不相同且均为 [1,n][1,n] 内的整数。

如果一个点的发生顺序恰为其父亲的发生顺序加一,称这两个事件是紧密相连的。只保留紧密相连的树边,会得到若干个连通块,爱音认为每个连通块的权值是其内所有点权的异或和,而这个发生顺序设计方案的价值是所有连通块的权值乘积。

爱音想知道所有合法发生顺序设计方案的价值和,请你帮她求出该值,对 998244353998244353 取模。

输入格式

第一行输入 nn。

第二行输入 nn 个数,第 ii 个数为 aia_i。

接下来输入 n−1n-1 行,每行两个数 x,yx,y 表示存在树边 (x,y)(x,y)。

输出格式

输出一行一个整数表示答案。

4
0 9 0 8
1 2
2 3
2 4
72
9
1 2 3 4 5 6 7 8 9
1 2
1 3
2 4
3 5
2 6
6 7
6 8
1 9
190486596

提示

【数据范围】

对所有数据,满足 n≤1000,0≤a<264n\le 1000,0\le a<2^{64}。

【样例解释 #1】

两种合法的发生顺序设计方式及其价值分别为:

  • 1,2,3,41,2,3,4,两个连通块为 {1,2,3},{4}\{1,2,3\},\{4\},价值为 9×8=729\times 8=72。
  • 1,2,4,31,2,4,3,两个连通块为 {1,2,4},{3}\{1,2,4\},\{3\},价值为 1×0=01\times 0=0。

总价值为 72+0=7272+0=72。


看来已经不需要我了吧。