Problem C: Xor Tree Problem C: 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.