Deblo

Interview

Time limit1sMemory limit512 MB

Summary

Given a tree with numbers on its nodes, add up the XOR of every node-value along every path between two nodes, counting single-node paths too.

Level: Medium6 of 10
Topics: Tree, Bit manipulation, DFS, Math
Solved: No attempts yet

Problem

About thirty years ago, young Krešo took part in the national informatics competition for the first time. As today, the opening of the competition consisted of a series of speakers who tried to show the contestants the importance of the event through motivational messages. The audience applauded enthusiastically every few seconds, but one sentence irritated Krešo. One of the speakers claimed he appreciated the logical operation AND more than the logical operation OR because, regardless of the winner's identity, to him both Mirko and Slavko were winners of the national competition, instead of the winner being Mirko or Slavko. Krešo lost his temper, stood up and began explaining to the audience that this is an operation known as exclusive OR (commonly XOR). After his lecture, he gave the distinguished speaker the following task to check his understanding.

A tree with N nodes is given, and each node has a value assigned to it. The value of a path in that tree is defined as the exclusive OR of the values of all nodes on that path. Determine the sum of the values of all paths of the tree, including paths that contain only one node.

Thirty years later, Krešo has finally persuaded the authors of the COCI tasks to include this task in one of the rounds. Help us restore Krešo's faith in the future of competitive programming.

Input

The first line contains a positive integer N (1 ≤ N ≤ 100 000), the number of nodes in the tree.

The second line contains N integers vi (0 ≤ vi ≤ 3 000 000) separated by spaces, the i-th value being the value of the i-th node.

The following (N-1) lines contain two numbers aj and bj (1 ≤ aj, bj ≤ N) indicating that there is an edge between nodes aj and bj.

Output

Print the required sum of the values of all tree paths.

Hint

Exclusive OR (⊕) is a binary operation applied separately to each pair of corresponding bits of its two operands, so that a bit in the result is set to 1 if and only if that bit is set to 1 in exactly one operand.

Examples3

Example 1
Input
```
3
1 2 3
1 2
2 3
```
Expected output
```
10
```
Example 2
Input
```
5
2 3 4 2 1
1 2
1 3
3 4
3 5
```
Expected output
```
64
```
Example 3
Input
```
6
5 4 1 3 3 3
3 1
3 5
4 3
4 2
2 6
```
Expected output
```
85
```