14061406 SUSTech Online Judge
Problem 1406 --Xor Tree

1406: Xor Tree

Time Limit: 5 Sec  Memory Limit: 256 MB
Submit: 305  Solved: 13
[Submit][Status][Web Board]

Description

To celebrate the 10th anniversary of SUSTech, Alice buys a tree \(T\) which has \(n\) nodes. The value of each node \(i\) on that tree is \(a_i\).
We define a chain \(L(u, v)\) is the sequence of the nodes in the shortest path from \(u\) to \(v\) (\(u < v\)).
We define a subchain of \(L(u,v)\) is \(L(u',v')\) if \(u',v' \in L(u,v)\) and \(u' < v'\). It means \(L(u', v') \subseteq L(u, v)\).
In addition, we define 
\(f(u, v)=(XOR_{x \in L(u, v)} a_x)^2\).
\(g(u,v)=\sum_{L(u',v') \subseteq L(u,v)} f(u',v')\).
Here, \(XOR_{v \in S}\) means bitwise exclusive or of all values of the set \(S\).
Now Alice wants to compute {\(\sum_{i=1}^n\sum_{j=i+1}^{n} g(i,j)\) mod \(998244353\)}, can you help her?

Input

The first line contains an integer \(n\).
The next line contains \(n\) integer \(a_1, a_2, \ldots, a_n\), indicating the value of each node.
And then \(n-1\) lines follows, each line contains two integer \(u_i,v_i\), indicating there is an edge between \(u_i\) and \(v_i\).
\(1\leq n \leq 10^5\), \(1\le u_i, v_i \le n\), \(1 \le a_i \le 10^9\).

Output

A single line, print out one integer representing the answer.

Sample Input

3
1 2 3
1 2
1 3

Sample Output

26

HINT

You can get:

f(1,2)=(a[1] xor a[2])*(a[1] xor a[2])=3*3=9

f(1,3)=(a[1] xor a[3])*(a[1] xor a[3])=2*2=4

f(2,3)=(a[2] xor a[1] xor a[3])*(a[2] xor a[1] xor a[3])=0*0=0

The Subchain of L(2,3) is: L(1,2),L(1,3),L(2,3).

So g(2,3)=f(1,2)+f(1,3)+f(2,3)=3*3+0*0+2*2=13.

The Subchain of L(1,2) is: L(1,2).

So g(1,2)=f(1,2)=3*3=9.

The Subchain of L(1,3) is: L(1,3).

So g(1,3)=f(1,3)=2*2=4.

So the answer is 13+9+4=26.

Source

 

[Submit][Status]