[R55F]异或的下传 - 代码源竞赛平台

时空限制

2.5S/512M

题目描述

给定一棵包含 $n$ 个节点的有根树，树的根节点固定为 $1$ 号节点。每个节点 $i$ 都有一个给定的权值 $a_i$。

为了保证逻辑的完整性，我们额外规定 $0$ 号节点为根节点 $1$ 的父亲，且规定 $a_0 = 0$。

你需要从树中任意挑选三个互不相同的节点 $i, j, k$，并求出所有组合情况的函数 $f$ 之和。即求：

$$\sum_{1 \le i < j < k \le n} f(i,j,k)$$

其中 $f(i,j,k) = a_i \oplus a_j \oplus a_k \oplus a_w$。 公式中的 $w$ 是节点 $i, j, k$ 的最近公共祖先的父亲节点，$\oplus$ 表示按位异或运算。

由于最终的答案可能很大，你需要输出答案对 $998244353$ 取模后的结果。

格式

输入格式

第一行包含一个整数 $n$，表示树的节点个数。

第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$，分别表示每个节点的权值。

接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$，表示节点 $u$ 和节点 $v$ 之间有一条边。

输出格式

输出仅包含一行一个整数，表示计算结果对 $998244353$ 取模后的值。

样例

样例输入 #1

5
1 3 2 7 6
1 2
1 3
2 4
2 5

样例输出 #1

37

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n\le$
$1$	$30$	$200$
$2$	$40$	$1000$
$3$	$30$	$2\times 10^5$

对于 $100\%$ 的数据，$3 \leq n \leq 2 \times 10^5$，$1 \le a_i < 2^{30}$，输入保证构成一棵合法的树。