Sum of XOR on All Paths in a Tree

Given a tree with \(n\) nodes, where each node has an associated weight \(a_i\). A path in the tree is defined as any sequence of distinct nodes where each consecutive pair of nodes is connected by an edge (a single node is also considered a valid path).

The weight of a path \(P = [v_1, v_2, \dots, v_k]\) is defined as the XOR (exclusive OR) of all its node weights:

\[ XOR(P) = a_{v_1} \oplus a_{v_2} \oplus \cdots \oplus a_{v_k}. \]

Your task is to compute the sum of \(XOR(P)\) over all possible paths in the tree.

inputFormat

The input consists of multiple lines:

1. The first line contains an integer (n) representing the number of nodes in the tree.
2. The second line contains (n) integers (a_1, a_2, \dots, a_n), where (a_i) is the weight of the (i)-th node.
3. Each of the next (n-1) lines contains two integers (u) and (v), denoting an undirected edge between node (u) and node (v).

outputFormat

Output a single integer which is the sum of the XOR values for all paths in the tree.

sample

2
3 5
1 2

14