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)$$.
$$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.