P5538 [XR-3] Namid[A]me

X gives you a tree with $n$ nodes, and each node has a weight. You need to compute the value of the following expression modulo $786433$: $\sum_{1\leq u\leq v\leq n}f(u,v)^{f(u,v)}$ Here, $f(u,v)$ is the value obtained by taking the bitwise AND of the weights of all nodes on the shortest path from $u$ to $v$. Hint: To make calculation easier, we define $0^0=0$. Also, $786433$ is a prime number and an uncommon NTT modulus, whose primitive root is $10$. If you do not know what NTT is or what a primitive root is, you can ignore this hint.

The first line contains a positive integer $n$, the number of nodes in the tree. The second line contains $n$ positive integers $a_{1\dots n}$, where $a_i$ is the weight of node $i$. The next $n-1$ lines each contain two positive integers $u,v$, meaning there is an edge between node $u$ and node $v$. **Constraints:** - $2 \le n \le 2 \times 10^5$. - For all $i$ satisfying $1\le i \le n$, $1 \le a_i < 2^{30}$. - $1 \le u,v \le n, u \ne v$. - Let $d$ be the number of leaves in the tree (nodes with degree $1$). The testdata guarantees that $4\le n \cdot d \le 3 \times 10 ^ 6$.

Output one integer on one line, the answer modulo $786433$.

Translated by ChatGPT 5