题目描述
小 X 给了你一棵 n 个点的树,点有点权。
你需要求出下列式子模 786433 的值:
∑1≤u≤v≤nf(u,v)f(u,v)
其中 f(u,v) 表示 u 到 v 的最短路径上所有点的点权按位与在一起之后的值。
提示:为了方便你的计算,这里我们认为 00=0。另外,786433 是一个质数,同时也是一个不常用的 NTT 模数,它的原根为 10,如果你不知道什么是 NTT 或者不知道什么是原根,你可以忽略这个提示。
输入格式
第一行一个正整数 n,表示树的点数。
第二行 n 个正整数 a1…n,其中 ai 表示编号为 i 的点的点权。
接下来 n−1 行,每行 2 个正整数 u,v,表示编号为 u 和编号为 v 的点之间有一条边。
数据范围:
- 2≤n≤2×105。
- 对于所有满足 1≤i≤n 的 i 都有 1≤ai<230。
- 1≤u,v≤n,u=v。
- 设 d 为树中叶子(度数为 1 的点)的个数,数据保证 4≤n⋅d≤3×106。
输出格式
一行一个整数,表示答案对 786433 取模后的值。