#P5538. 【XR-3】Namid[A] me

    ID: 4834 远端评测题 3000ms 250MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>图论O2优化树的应用位运算,按位

【XR-3】Namid[A] me

题目描述

小 X 给了你一棵 nn 个点的树,点有点权。

你需要求出下列式子模 786433786433 的值:

1uvnf(u,v)f(u,v)\sum_{1\leq u\leq v\leq n}f(u,v)^{f(u,v)}

其中 f(u,v)f(u,v) 表示 uuvv 的最短路径上所有点的点权按位与在一起之后的值。

提示:为了方便你的计算,这里我们认为 00=00^0=0。另外,786433786433 是一个质数,同时也是一个不常用的 NTT 模数,它的原根为 1010,如果你不知道什么是 NTT 或者不知道什么是原根,你可以忽略这个提示。

输入格式

第一行一个正整数 nn,表示树的点数。

第二行 nn 个正整数 a1na_{1\dots n},其中 aia_i 表示编号为 ii 的点的点权。

接下来 n1n-1 行,每行 22 个正整数 u,vu,v,表示编号为 uu 和编号为 vv 的点之间有一条边。

数据范围:

  • 2n2×1052 \le n \le 2 \times 10^5
  • 对于所有满足 1in1\le i \le nii 都有 1ai<2301 \le a_i < 2^{30}
  • 1u,vn,uv1 \le u,v \le n, u \ne v
  • dd 为树中叶子(度数为 11 的点)的个数,数据保证 4nd3×1064\le n \cdot d \le 3 \times 10 ^ 6

输出格式

一行一个整数,表示答案对 786433786433 取模后的值。

10
15 50 89 9 38 73 38 23 6 52
2 1
3 2
4 2
5 3
6 3
7 5
8 7
9 1
10 7

54184

20
17 56 72 12 16 43 33 8 28 90 21 12 7 43 55 95 25 65 63 77
2 1
3 2
4 1
5 3
6 5
7 1
8 7
9 7
10 3
11 5
12 7
13 5
14 7
15 11
16 6
17 3
18 15
19 15
20 13

503636