Xorability P43845


Statement
 

pdf   zip

thehtml

Consider a tree with n nodes numbered from 1 to n, rooted at 1. Each node i has a natural label ℓi. Given two nodes u and v, define X(u, v) as the exclusive or (^ in C++) of all the ℓi in the path from u to v.

Let L be the set of leaves of the tree. Please compute ∑v ∈ L X(1, v).

Input

Input consists of several trees, each with the number of nodes n, followed by ℓ1, …, ℓn, followed by n − 1 pairs of nodes describing the edges of the tree. Assume 2 ≤ n ≤ 105, and 0 ≤ li ≤ 109.

Output

For each tree, print the required sum.

Public test cases

  • Input

    3
2 7 3
1 2  2 3
6
18 6 9 12 15 3
1 6  6 5  3 6  2 3  3 4
7
1 2 3 4 5 6 7
1 4  1 5  2 1  4 6  2 3  2 7
4
1000000000 0 0 0
2 1  3 1  4 1

    Output

    6
80
11
3000000000
    • Information
    Author
    Ángel García
    Language
    English
    Official solutions
    C++
    User solutions
    C++