Tree Subtree XOR Value Sum

You are given a rooted tree \(T\) with \(n\) nodes numbered from \(1\) to \(n\), where node \(1\) is the root. Each node \(i\) has a positive integer weight \(v_i\). For a node \(x\), let its subtree (including \(x\) itself) have nodes \(c_1, c_2, \dots, c_k\). The value of node \(x\) is defined as:

[ val(x)= (v_{c_1}+d(c_1,x)) \oplus (v_{c_2}+d(c_2,x)) \oplus \cdots \oplus (v_{c_k}+d(c_k,x)) ]

Here, \(d(x,y)\) denotes the number of edges on the unique simple path between nodes \(x\) and \(y\) in the tree (with \(d(x,x)=0\)), and \(\oplus\) represents the bitwise XOR operation.

Your task is to compute the sum

[ \sum_{i=1}^n val(i) ]

over all nodes (i) in the tree.

Note: The tree is given as an undirected tree with \(n-1\) edges and is rooted at node \(1\). You must treat the given tree as rooted at \(1\).

inputFormat

The first line contains an integer \(n\) (the number of nodes).

The second line contains \(n\) positive integers \(v_1, v_2, \ldots, v_n\), where \(v_i\) is the weight of node \(i\).

Each of the next \(n-1\) lines contains two integers \(u\) and \(v\), representing an edge between nodes \(u\) and \(v\).

outputFormat

Output a single integer representing \(\sum_{i=1}^n val(i)\).

sample

3
1 2 3
1 2
1 3

11