Mahmoud and a xor trip (Codeforces 766E)
Tags: Math, bitmasks

Mahmoud and Ehab live in a country with n cities numbered from 1 to n and connected by n - 1 undirected roads. It's guaranteed that you can reach any city from any other using these roads. Each city has a number ai attached to it.We define the distance from city x to city y as the xor of numbers attached to the cities on the path from x to y (including both x and y). In other words if values attached to the cities on the path from x to y form an array p of length l then the distance between them is , where  is bitwise xor operation.Mahmoud and Ehab want to choose two cities and make a journey from one to another. The index of the start city is always less than or equal to the index of the finish city (they may start and finish in the same city and in this case the distance equals the number attached to that city). They can't determine the two cities so they try every city as a start and every city with greater index as a finish. They want to know the total distance between all pairs of cities.

Input: The first line contains integer n (1 ≤ n ≤ 105) — the number of cities in Mahmoud and Ehab's country.Then the second line contains n integers a1, a2, ..., an (0 ≤ ai ≤ 106) which represent the numbers attached to the cities. Integer ai is attached to the city i.Each of the next n  -  1 lines contains two integers u and v (1  ≤  u,  v  ≤  n, u  ≠  v), denoting that there is an undirected road between cities u and v. It's guaranteed that you can reach any city from any other using these roads.

Output: Output one number denoting the total distance between all pairs of cities.

Note: A bitwise xor takes two bit integers of equal length and performs the logical xor operation on each pair of corresponding bits. The result in each position is 1 if only the first bit is 1 or only the second bit is 1, but will be 0 if both are 0 or both are 1. You can read more about bitwise xor operation here: https://en.wikipedia.org/wiki/Bitwise_operation#XOR.In the first sample the available paths are:  city 1 to itself with a distance of 1,  city 2 to itself with a distance of 2,  city 3 to itself with a distance of 3,  city 1 to city 2 with a distance of ,  city 1 to city 3 with a distance of ,  city 2 to city 3 with a distance of .  The total distance between all pairs of cities equals 1 + 2 + 3 + 3 + 0 + 1 = 10.

Sample Inputs:
3
1 2 3
1 2
2 3

5
1 2 3 4 5
1 2
2 3
3 4
3 5

5
10 9 8 7 6
1 2
2 3
3 4
3 5

Sample Outputs:
10

52

131

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def bfs(s):
    (q, k) = ([s], 0)
    visit = [0] * (n + 1)
    visit[s] = 1
    parent = [0] * (n + 1)
    child = [[] for _ in range(n + 1)]
    for k in range(n):
        i = q[k]
        bi = b[i]
        for j in G[i]:
            if not visit[j]:
                b[j] ^= bi
                q.append(j)
                visit[j] = 1
                parent[j] = i
                child[i].append(j)
    return (q, parent, child)
n = int(input())
a = [0] + list(map(int, input().split()))
b = list(a)
G = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    (u, v) = map(int, input().split())
    G[u].append(v)
    G[v].append(u)
(q, parent, child) = bfs(1)
q.reverse()
cnt = [1] * (n + 1)
for i in q:
    cnt[parent[i]] += cnt[i]
p = 1
ans = 0
for _ in range(20):
    dp = [0] * (n + 1)
    (c, c0) = (0, 0)
    for j in q:
        if b[j] & p:
            dp[j] += 1
        dp[parent[j]] += dp[j]
        (u, v) = (0, 0)
        if a[j] & p:
            c0 += 1
            for k in child[j]:
                (u0, v0) = (cnt[k] - dp[k], dp[k])
                c += u * u0 + v * v0
                u += u0
                v += v0
        else:
            for k in child[j]:
                (u0, v0) = (cnt[k] - dp[k], dp[k])
                c += u * v0 + v * u0
                u += u0
                v += v0
        if a[j] & p and (not b[j] & p) or (not a[j] & p and b[j] & p):
            c += u
        else:
            c += v
    ans += (c + c0) * p
    p *= 2
print(ans)

Solution (Python):
import sys
readline = sys.stdin.readline

class Graph:

    def __init__(self, V, edges=False, graph=False, directed=False, weighted=False):
        self.V = V
        self.directed = directed
        self.weighted = weighted
        if not graph:
            self.edges = edges
            self.graph = [[] for i in range(self.V)]
            if weighted:
                for (i, j, d) in self.edges:
                    self.graph[i].append((j, d))
                    if not self.directed:
                        self.graph[j].append((i, d))
            else:
                for (i, j) in self.edges:
                    self.graph[i].append(j)
                    if not self.directed:
                        self.graph[j].append(i)
        else:
            self.graph = graph
            self.edges = []
            for i in range(self.V):
                if self.weighted:
                    for (j, d) in self.graph[i]:
                        if self.directed or (not self.directed and i <= j):
                            self.edges.append((i, j, d))
                else:
                    for j in self.graph[i]:
                        if self.directed or (not self.directed and i <= j):
                            self.edges.append((i, j))

    def SS_BFS(self, s, bipartite_graph=False, linked_components=False, parents=False, unweighted_dist=False, weighted_dist=False):
        seen = [False] * self.V
        seen[s] = True
        if linked_components:
            lc = [s]
        if parents:
            ps = [None] * self.V
            ps[s] = s
        if unweighted_dist or bipartite_graph:
            uwd = [float('inf')] * self.V
            uwd[s] = 0
        if weighted_dist:
            wd = [float('inf')] * self.V
            wd[s] = 0
        queue = deque([s])
        while queue:
            x = queue.popleft()
            for y in self.graph[x]:
                if self.weighted:
                    (y, d) = y
                if not seen[y]:
                    seen[y] = True
                    queue.append(y)
                    if linked_components:
                        lc.append(y)
                    if parents:
                        ps[y] = x
                    if unweighted_dist or bipartite_graph:
                        uwd[y] = uwd[x] + 1
                    if weighted_dist:
                        wd[y] = wd[x] + d
        if bipartite_graph:
            bg = [[], []]
            for tpl in self.edges:
                (i, j) = tpl[:2] if self.weighted else tpl
                if type(uwd[i]) == float or type(uwd[j]) == float:
                    continue
                if not uwd[i] % 2 ^ uwd[j] % 2:
                    bg = False
                    break
            else:
                for x in range(self.V):
                    if type(uwd[x]) == float:
                        continue
                    bg[uwd[x] % 2].append(x)
        tpl = ()
        if bipartite_graph:
            tpl += (bg,)
        if linked_components:
            tpl += (lc,)
        if parents:
            tpl += (ps,)
        if unweighted_dist:
            tpl += (uwd,)
        if weighted_dist:
            tpl += (wd,)
        if len(tpl) == 1:
            tpl = tpl[0]
        return tpl

    def AP_BFS(self, bipartite_graph=False, linked_components=False, parents=False):
        seen = [False] * self.V
        if bipartite_graph:
            bg = [None] * self.V
            cnt = -1
        if linked_components:
            lc = []
        if parents:
            ps = [None] * self.V
        for s in range(self.V):
            if seen[s]:
                continue
            seen[s] = True
            if bipartite_graph:
                cnt += 1
                bg[s] = (cnt, 0)
            if linked_components:
                lc.append([s])
            if parents:
                ps[s] = s
            queue = deque([s])
            while queue:
                x = queue.popleft()
                for y in self.graph[x]:
                    if self.weighted:
                        (y, d) = y
                    if not seen[y]:
                        seen[y] = True
                        queue.append(y)
                        if bipartite_graph:
                            bg[y] = (cnt, bg[x][1] ^ 1)
                        if linked_components:
                            lc[-1].append(y)
                        if parents:
                            ps[y] = x
        if bipartite_graph:
            bg_ = bg
            bg = [[[], []] for i in range(cnt + 1)]
            for tpl in self.edges:
                (i, j) = tpl[:2] if self.weighted else tpl
                if not bg_[i][1] ^ bg_[j][1]:
                    bg[bg_[i][0]] = False
            for x in range(self.V):
                if bg[bg_[x][0]]:
                    bg[bg_[x][0]][bg_[x][1]].append(x)
        tpl = ()
        if bipartite_graph:
            tpl += (bg,)
        if linked_components:
            tpl += (lc,)
        if parents:
            tpl += (ps,)
        if len(tpl) == 1:
            tpl = tpl[0]
        return tpl

    def SS_DFS(self, s, bipartite_graph=False, cycle_detection=False, directed_acyclic=False, euler_tour=False, linked_components=False, parents=False, postorder=False, preorder=False, subtree_size=False, topological_sort=False, unweighted_dist=False, weighted_dist=False):
        seen = [False] * self.V
        finished = [False] * self.V
        if directed_acyclic or cycle_detection or topological_sort:
            dag = True
        if euler_tour:
            et = []
        if linked_components:
            lc = []
        if parents or cycle_detection or subtree_size:
            ps = [None] * self.V
            ps[s] = s
        if postorder or topological_sort:
            post = []
        if preorder:
            pre = []
        if subtree_size:
            ss = [1] * self.V
        if unweighted_dist or bipartite_graph:
            uwd = [float('inf')] * self.V
            uwd[s] = 0
        if weighted_dist:
            wd = [float('inf')] * self.V
            wd[s] = 0
        stack = [(s, 0)] if self.weighted else [s]
        while stack:
            if self.weighted:
                (x, d) = stack.pop()
            else:
                x = stack.pop()
            if not seen[x]:
                seen[x] = True
                stack.append((x, d) if self.weighted else x)
                if euler_tour:
                    et.append(x)
                if linked_components:
                    lc.append(x)
                if preorder:
                    pre.append(x)
                for y in self.graph[x]:
                    if self.weighted:
                        (y, d) = y
                    if not seen[y]:
                        stack.append((y, d) if self.weighted else y)
                        if parents or cycle_detection or subtree_size:
                            ps[y] = x
                        if unweighted_dist or bipartite_graph:
                            uwd[y] = uwd[x] + 1
                        if weighted_dist:
                            wd[y] = wd[x] + d
                    elif not finished[y]:
                        if (directed_acyclic or cycle_detection or topological_sort) and dag:
                            dag = False
                            if cycle_detection:
                                cd = (y, x)
            elif not finished[x]:
                finished[x] = True
                if euler_tour:
                    et.append(~x)
                if postorder or topological_sort:
                    post.append(x)
                if subtree_size:
                    for y in self.graph[x]:
                        if y == ps[x]:
                            continue
                        ss[x] += ss[y]
        if bipartite_graph:
            bg = [[], []]
            for tpl in self.edges:
                (i, j) = tpl[:2] if self.weighted else tpl
                if type(uwd[i]) == float or type(uwd[j]) == float:
                    continue
                if not uwd[i] % 2 ^ uwd[j] % 2:
                    bg = False
                    break
            else:
                for x in range(self.V):
                    if type(uwd[x]) == float:
                        continue
                    bg[uwd[x] % 2].append(x)
        tpl = ()
        if bipartite_graph:
            tpl += (bg,)
        if cycle_detection:
            if dag:
                cd = []
            else:
                (y, x) = cd
                cd = self.Route_Restoration(y, x, ps)
            tpl += (cd,)
        if directed_acyclic:
            tpl += (dag,)
        if euler_tour:
            tpl += (et,)
        if linked_components:
            tpl += (lc,)
        if parents:
            tpl += (ps,)
        if postorder:
            tpl += (post,)
        if preorder:
            tpl += (pre,)
        if subtree_size:
            tpl += (ss,)
        if topological_sort:
            if dag:
                tp_sort = post[::-1]
            else:
                tp_sort = []
            tpl += (tp_sort,)
        if unweighted_dist:
            tpl += (uwd,)
        if weighted_dist:
            tpl += (wd,)
        if len(tpl) == 1:
            tpl = tpl[0]
        return tpl

    def AP_DFS(self, bipartite_graph=False, cycle_detection=False, directed_acyclic=False, euler_tour=False, linked_components=False, parents=False, postorder=False, preorder=False, topological_sort=False):
        seen = [False] * self.V
        finished = [False] * self.V
        if bipartite_graph:
            bg = [None] * self.V
            cnt = -1
        if directed_acyclic or cycle_detection or topological_sort:
            dag = True
        if euler_tour:
            et = []
        if linked_components:
            lc = []
        if parents or cycle_detection:
            ps = [None] * self.V
        if postorder or topological_sort:
            post = []
        if preorder:
            pre = []
        for s in range(self.V):
            if seen[s]:
                continue
            if bipartite_graph:
                cnt += 1
                bg[s] = (cnt, 0)
            if linked_components:
                lc.append([])
            if parents:
                ps[s] = s
            stack = [(s, 0)] if self.weighted else [s]
            while stack:
                if self.weighted:
                    (x, d) = stack.pop()
                else:
                    x = stack.pop()
                if not seen[x]:
                    seen[x] = True
                    stack.append((x, d) if self.weighted else x)
                    if euler_tour:
                        et.append(x)
                    if linked_components:
                        lc[-1].append(x)
                    if preorder:
                        pre.append(x)
                    for y in self.graph[x]:
                        if self.weighted:
                            (y, d) = y
                        if not seen[y]:
                            stack.append((y, d) if self.weighted else y)
                            if bipartite_graph:
                                bg[y] = (cnt, bg[x][1] ^ 1)
                            if parents or cycle_detection:
                                ps[y] = x
                        elif not finished[y]:
                            if directed_acyclic and dag:
                                dag = False
                                if cycle_detection:
                                    cd = (y, x)
                elif not finished[x]:
                    finished[x] = True
                    if euler_tour:
                        et.append(~x)
                    if postorder or topological_sort:
                        post.append(x)
        if bipartite_graph:
            bg_ = bg
            bg = [[[], []] for i in range(cnt + 1)]
            for tpl in self.edges:
                (i, j) = tpl[:2] if self.weighted else tpl
                if not bg_[i][1] ^ bg_[j][1]:
                    bg[bg_[i][0]] = False
            for x in range(self.V):
                if bg[bg_[x][0]]:
                    bg[bg_[x][0]][bg_[x][1]].append(x)
        tpl = ()
        if bipartite_graph:
            tpl += (bg,)
        if cycle_detection:
            if dag:
                cd = []
            else:
                (y, x) = cd
                cd = self.Route_Restoration(y, x, ps)
            tpl += (cd,)
        if directed_acyclic:
            tpl += (dag,)
        if euler_tour:
            tpl += (et,)
        if linked_components:
            tpl += (lc,)
        if parents:
            tpl += (ps,)
        if postorder:
            tpl += (post,)
        if preorder:
            tpl += (pre,)
        if topological_sort:
            if dag:
                tp_sort = post[::-1]
            else:
                tp_sort = []
            tpl += (tp_sort,)
        if len(tpl) == 1:
            tpl = tpl[0]
        return tpl

    def Tree_Diameter(self, weighted=False):

        def Farthest_Point(u):
            dist = self.SS_BFS(u, weighted_dist=True) if weighted else self.SS_BFS(u, unweighted_dist=True)
            fp = 0
            for i in range(self.V):
                if dist[fp] < dist[i]:
                    fp = i
            return (fp, dist[fp])
        (u, d) = Farthest_Point(0)
        (v, d) = Farthest_Point(u)
        return (u, v, d)

    def SCC(self):
        reverse_graph = [[] for i in range(self.V)]
        for tpl in self.edges:
            (i, j) = tpl[:2] if self.weighted else tpl
            reverse_graph[j].append(i)
        postorder = self.AP_DFS(postorder=True)
        scc = []
        seen = [False] * self.V
        for s in postorder[::-1]:
            if seen[s]:
                continue
            queue = deque([s])
            seen[s] = True
            lst = []
            while queue:
                x = queue.popleft()
                lst.append(x)
                for y in reverse_graph[x]:
                    if self.weighted:
                        y = y[0]
                    if not seen[y]:
                        seen[y] = True
                        queue.append(y)
            scc.append(lst)
        return scc

    def Build_LCA(self, s):
        (self.euler_tour, self.parents, depth) = self.SS_DFS(s, euler_tour=True, parents=True, unweighted_dist=True)
        self.dfs_in_index = [None] * self.V
        self.dfs_out_index = [None] * self.V
        for (i, x) in enumerate(self.euler_tour):
            if x >= 0:
                self.dfs_in_index[x] = i
            else:
                self.dfs_out_index[~x] = i
        self.ST = Segment_Tree(2 * self.V, lambda x, y: min(x, y), float('inf'))
        lst = [None] * 2 * self.V
        for i in range(2 * self.V):
            if self.euler_tour[i] >= 0:
                lst[i] = depth[self.euler_tour[i]]
            else:
                lst[i] = depth[self.parents[~self.euler_tour[i]]]
        self.ST.Build(lst)

    def LCA(self, a, b):
        m = min(self.dfs_in_index[a], self.dfs_in_index[b])
        M = max(self.dfs_in_index[a], self.dfs_in_index[b])
        x = self.euler_tour[self.ST.Fold_Index(m, M + 1)]
        if x >= 0:
            return x
        else:
            return self.parents[~x]

    def Dijkstra(self, s, route_restoration=False):
        dist = [float('inf')] * self.V
        dist[s] = 0
        hq = [(0, s)]
        if route_restoration:
            parents = [None] * self.V
            parents[s] = s
        while hq:
            (dx, x) = heapq.heappop(hq)
            if dist[x] < dx:
                continue
            for (y, dy) in self.graph[x]:
                if dist[y] > dx + dy:
                    dist[y] = dx + dy
                    if route_restoration:
                        parents[y] = x
                    heapq.heappush(hq, (dist[y], y))
        if route_restoration:
            return (dist, parents)
        else:
            return dist

    def Bellman_Ford(self, s, route_restoration=False):
        dist = [float('inf')] * self.V
        dist[s] = 0
        if route_restoration:
            parents = [s] * self.V
        for _ in range(self.V - 1):
            for (i, j, d) in self.edges:
                if dist[j] > dist[i] + d:
                    dist[j] = dist[i] + d
                    if route_restoration:
                        parents[j] = i
                if not self.directed and dist[i] > dist[j] + d:
                    dist[i] = dist[j] + d
                    if route_restoration:
                        parents[i] = j
        negative_cycle = []
        for (i, j, d) in self.edges:
            if dist[j] > dist[i] + d:
                negative_cycle.append(j)
            if not self.directed and dist[i] > dist[j] + d:
                negative_cycle.append(i)
        if negative_cycle:
            is_negative_cycle = [False] * self.V
            for i in negative_cycle:
                if is_negative_cycle[i]:
                    continue
                else:
                    queue = deque([i])
                    is_negative_cycle[i] = True
                    while queue:
                        x = queue.popleft()
                        for (y, d) in self.graph[x]:
                            if not is_negative_cycle[y]:
                                queue.append(y)
                                is_negative_cycle[y] = True
                                if route_restoration:
                                    parents[y] = x
            for i in range(self.V):
                if is_negative_cycle[i]:
                    dist[i] = -float('inf')
        if route_restoration:
            return (dist, parents)
        else:
            return dist

    def Warshall_Floyd(self, route_restoration=False):
        dist = [[float('inf')] * self.V for i in range(self.V)]
        for i in range(self.V):
            dist[i][i] = 0
        if route_restoration:
            parents = [[j for j in range(self.V)] for i in range(self.V)]
        for (i, j, d) in self.edges:
            if dist[i][j] > d:
                dist[i][j] = d
                if route_restoration:
                    parents[i][j] = i
            if not self.directed and dist[j][i] > d:
                dist[j][i] = d
                if route_restoration:
                    parents[j][i] = j
        for k in range(self.V):
            for i in range(self.V):
                for j in range(self.V):
                    if dist[i][j] > dist[i][k] + dist[k][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]
                        if route_restoration:
                            parents[i][j] = parents[k][j]
        for i in range(self.V):
            if dist[i][i] < 0:
                for j in range(self.V):
                    if dist[i][j] != float('inf'):
                        dist[i][j] = -float('inf')
        if route_restoration:
            return (dist, parents)
        else:
            return dist

    def Route_Restoration(self, s, g, parents):
        route = [g]
        while s != g and parents[g] != g:
            g = parents[g]
            route.append(g)
        route = route[::-1]
        return route

    def Kruskal(self):
        UF = UnionFind(self.V)
        sorted_edges = sorted(self.edges, key=lambda x: x[2])
        minimum_spnning_tree = []
        for (i, j, d) in sorted_edges:
            if not UF.Same(i, j):
                UF.Union(i, j)
                minimum_spnning_tree.append((i, j, d))
        return minimum_spnning_tree

    def Ford_Fulkerson(self, s, t):
        max_flow = 0
        residual_graph = [defaultdict(int) for i in range(self.V)]
        if self.weighted:
            for (i, j, d) in self.edges:
                if not d:
                    continue
                residual_graph[i][j] += d
                if not self.directed:
                    residual_graph[j][i] += d
        else:
            for (i, j) in self.edges:
                residual_graph[i][j] += 1
                if not self.directed:
                    residual_graph[j][i] += 1
        while True:
            parents = [None] * self.V
            parents[s] = s
            seen = [False] * self.V
            seen[s] = True
            queue = deque([s])
            while queue:
                x = queue.popleft()
                for y in residual_graph[x].keys():
                    if not seen[y]:
                        seen[y] = True
                        queue.append(y)
                        parents[y] = x
                        if y == t:
                            tt = t
                            while tt != s:
                                residual_graph[parents[tt]][tt] -= 1
                                residual_graph[tt][parents[tt]] += 1
                                if not residual_graph[parents[tt]][tt]:
                                    residual_graph[parents[tt]].pop(tt)
                                tt = parents[tt]
                            max_flow += 1
                            break
                else:
                    continue
                break
            else:
                break
        return max_flow

    def BFS(self, s):
        seen = [False] * self.V
        seen[s] = True
        queue = deque([s])
        while queue:
            x = queue.popleft()
            for y in self.graph[x]:
                if self.weighted:
                    (y, d) = y
                if not seen[y]:
                    seen[y] = True
                    queue.append(y)
        return

    def DFS(self, s):
        seen = [False] * self.V
        finished = [False] * self.V
        stack = [(s, 0)] if self.weighted else [s]
        while stack:
            if self.weighted:
                (x, d) = stack.pop()
            else:
                x = stack.pop()
            if not seen[x]:
                seen[x] = True
                stack.append((x, d) if self.weighted else x)
                for y in self.graph[x]:
                    if self.weighted:
                        (y, d) = y
                    if not seen[y]:
                        stack.append((y, d) if self.weighted else y)
            elif not finished[x]:
                finished[x] = True
        return
N = int(readline())
A = list(map(int, readline().split()))
edges = []
for i in range(N - 1):
    (u, v) = map(int, readline().split())
    u -= 1
    v -= 1
    edges.append((u, v))
G = Graph(N, edges=edges)
ans = 0
cnt0 = [[0] * 20 for a in A]
cnt1 = [[0] * 20 for a in A]
parents = G.SS_DFS(0, parents=True)
for x in G.SS_DFS(0, postorder=True):
    for i in range(20):
        for y in G.graph[x]:
            if y == parents[x]:
                continue
            cnt0[x][i] += cnt0[y][i]
            cnt1[x][i] += cnt1[y][i]
        if A[x] >> i & 1:
            ans += cnt0[x][i] * (cnt0[x][i] + 1) // 2 << i
            ans += cnt1[x][i] * (cnt1[x][i] - 1) // 2 << i
            ans += 1 << i
            for y in G.graph[x]:
                if y == parents[x]:
                    continue
                ans -= cnt0[y][i] * (cnt0[y][i] - 1) // 2 << i
                ans -= cnt1[y][i] * (cnt1[y][i] - 1) // 2 << i
            (cnt0[x][i], cnt1[x][i]) = (cnt1[x][i], cnt0[x][i])
            cnt1[x][i] += 1
        else:
            ans += (cnt0[x][i] + 1) * cnt1[x][i] << i
            for y in G.graph[x]:
                if y == parents[x]:
                    continue
                ans -= cnt0[y][i] * cnt1[y][i] << i
            cnt0[x][i] += 1
print(ans)

Solution (Python):
import bisect
import copy
import decimal
import fractions
import functools
import heapq
import itertools
import math
import random
import sys
from collections import Counter, deque, defaultdict
from functools import lru_cache, reduce
from heapq import heappush, heappop, heapify, heappushpop, _heappop_max, _heapify_max

def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap) - 1)

def _heappushpop_max(heap, item):
    if heap and item < heap[0]:
        (item, heap[0]) = (heap[0], item)
        heapq._siftup_max(heap, 0)
    return item
from math import gcd as GCD
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

class Graph:

    def __init__(self, V, edges=False, graph=False, directed=False, weighted=False):
        self.V = V
        self.directed = directed
        self.weighted = weighted
        if not graph:
            self.edges = edges
            self.graph = [[] for i in range(self.V)]
            if weighted:
                for (i, j, d) in self.edges:
                    self.graph[i].append((j, d))
                    if not self.directed:
                        self.graph[j].append((i, d))
            else:
                for (i, j) in self.edges:
                    self.graph[i].append(j)
                    if not self.directed:
                        self.graph[j].append(i)
        else:
            self.graph = graph
            self.edges = []
            for i in range(self.V):
                if self.weighted:
                    for (j, d) in self.graph[i]:
                        if self.directed or (not self.directed and i <= j):
                            self.edges.append((i, j, d))
                else:
                    for j in self.graph[i]:
                        if self.directed or (not self.directed and i <= j):
                            self.edges.append((i, j))

    def SS_BFS(self, s, bipartite_graph=False, linked_components=False, parents=False, unweighted_dist=False, weighted_dist=False):
        seen = [False] * self.V
        seen[s] = True
        if linked_components:
            lc = [s]
        if parents:
            ps = [None] * self.V
            ps[s] = s
        if unweighted_dist or bipartite_graph:
            uwd = [float('inf')] * self.V
            uwd[s] = 0
        if weighted_dist:
            wd = [float('inf')] * self.V
            wd[s] = 0
        queue = deque([s])
        while queue:
            x = queue.popleft()
            for y in self.graph[x]:
                if self.weighted:
                    (y, d) = y
                if not seen[y]:
                    seen[y] = True
                    queue.append(y)
                    if linked_components:
                        lc.append(y)
                    if parents:
                        ps[y] = x
                    if unweighted_dist or bipartite_graph:
                        uwd[y] = uwd[x] + 1
                    if weighted_dist:
                        wd[y] = wd[x] + d
        if bipartite_graph:
            bg = [[], []]
            for tpl in self.edges:
                (i, j) = tpl[:2] if self.weighted else tpl
                if type(uwd[i]) == float or type(uwd[j]) == float:
                    continue
                if not uwd[i] % 2 ^ uwd[j] % 2:
                    bg = False
                    break
            else:
                for x in range(self.V):
                    if type(uwd[x]) == float:
                        continue
                    bg[uwd[x] % 2].append(x)
        tpl = ()
        if bipartite_graph:
            tpl += (bg,)
        if linked_components:
            tpl += (lc,)
        if parents:
            tpl += (ps,)
        if unweighted_dist:
            tpl += (uwd,)
        if weighted_dist:
            tpl += (wd,)
        if len(tpl) == 1:
            tpl = tpl[0]
        return tpl

    def AP_BFS(self, bipartite_graph=False, linked_components=False, parents=False):
        seen = [False] * self.V
        if bipartite_graph:
            bg = [None] * self.V
            cnt = -1
        if linked_components:
            lc = []
        if parents:
            ps = [None] * self.V
        for s in range(self.V):
            if seen[s]:
                continue
            seen[s] = True
            if bipartite_graph:
                cnt += 1
                bg[s] = (cnt, 0)
            if linked_components:
                lc.append([s])
            if parents:
                ps[s] = s
            queue = deque([s])
            while queue:
                x = queue.popleft()
                for y in self.graph[x]:
                    if self.weighted:
                        (y, d) = y
                    if not seen[y]:
                        seen[y] = True
                        queue.append(y)
                        if bipartite_graph:
                            bg[y] = (cnt, bg[x][1] ^ 1)
                        if linked_components:
                            lc[-1].append(y)
                        if parents:
                            ps[y] = x
        if bipartite_graph:
            bg_ = bg
            bg = [[[], []] for i in range(cnt + 1)]
            for tpl in self.edges:
                (i, j) = tpl[:2] if self.weighted else tpl
                if not bg_[i][1] ^ bg_[j][1]:
                    bg[bg_[i][0]] = False
            for x in range(self.V):
                if bg[bg_[x][0]]:
                    bg[bg_[x][0]][bg_[x][1]].append(x)
        tpl = ()
        if bipartite_graph:
            tpl += (bg,)
        if linked_components:
            tpl += (lc,)
        if parents:
            tpl += (ps,)
        if len(tpl) == 1:
            tpl = tpl[0]
        return tpl

    def SS_DFS(self, s, bipartite_graph=False, cycle_detection=False, directed_acyclic=False, euler_tour=False, linked_components=False, parents=False, postorder=False, preorder=False, subtree_size=False, topological_sort=False, unweighted_dist=False, weighted_dist=False):
        seen = [False] * self.V
        finished = [False] * self.V
        if directed_acyclic or cycle_detection or topological_sort:
            dag = True
        if euler_tour:
            et = []
        if linked_components:
            lc = []
        if parents or cycle_detection or subtree_size:
            ps = [None] * self.V
            ps[s] = s
        if postorder or topological_sort:
            post = []
        if preorder:
            pre = []
        if subtree_size:
            ss = [1] * self.V
        if unweighted_dist or bipartite_graph:
            uwd = [float('inf')] * self.V
            uwd[s] = 0
        if weighted_dist:
            wd = [float('inf')] * self.V
            wd[s] = 0
        stack = [(s, 0)] if self.weighted else [s]
        while stack:
            if self.weighted:
                (x, d) = stack.pop()
            else:
                x = stack.pop()
            if not seen[x]:
                seen[x] = True
                stack.append((x, d) if self.weighted else x)
                if euler_tour:
                    et.append(x)
                if linked_components:
                    lc.append(x)
                if preorder:
                    pre.append(x)
                for y in self.graph[x]:
                    if self.weighted:
                        (y, d) = y
                    if not seen[y]:
                        stack.append((y, d) if self.weighted else y)
                        if parents or cycle_detection or subtree_size:
                            ps[y] = x
                        if unweighted_dist or bipartite_graph:
                            uwd[y] = uwd[x] + 1
                        if weighted_dist:
                            wd[y] = wd[x] + d
                    elif not finished[y]:
                        if (directed_acyclic or cycle_detection or topological_sort) and dag:
                            dag = False
                            if cycle_detection:
                                cd = (y, x)
            elif not finished[x]:
                finished[x] = True
                if euler_tour:
                    et.append(~x)
                if postorder or topological_sort:
                    post.append(x)
                if subtree_size:
                    for y in self.graph[x]:
                        if y == ps[x]:
                            continue
                        ss[x] += ss[y]
        if bipartite_graph:
            bg = [[], []]
            for tpl in self.edges:
                (i, j) = tpl[:2] if self.weighted else tpl
                if type(uwd[i]) == float or type(uwd[j]) == float:
                    continue
                if not uwd[i] % 2 ^ uwd[j] % 2:
                    bg = False
                    break
            else:
                for x in range(self.V):
                    if type(uwd[x]) == float:
                        continue
                    bg[uwd[x] % 2].append(x)
        tpl = ()
        if bipartite_graph:
            tpl += (bg,)
        if cycle_detection:
            if dag:
                cd = []
            else:
                (y, x) = cd
                cd = self.Route_Restoration(y, x, ps)
            tpl += (cd,)
        if directed_acyclic:
            tpl += (dag,)
        if euler_tour:
            tpl += (et,)
        if linked_components:
            tpl += (lc,)
        if parents:
            tpl += (ps,)
        if postorder:
            tpl += (post,)
        if preorder:
            tpl += (pre,)
        if subtree_size:
            tpl += (ss,)
        if topological_sort:
            if dag:
                tp_sort = post[::-1]
            else:
                tp_sort = []
            tpl += (tp_sort,)
        if unweighted_dist:
            tpl += (uwd,)
        if weighted_dist:
            tpl += (wd,)
        if len(tpl) == 1:
            tpl = tpl[0]
        return tpl

    def AP_DFS(self, bipartite_graph=False, cycle_detection=False, directed_acyclic=False, euler_tour=False, linked_components=False, parents=False, postorder=False, preorder=False, topological_sort=False):
        seen = [False] * self.V
        finished = [False] * self.V
        if bipartite_graph:
            bg = [None] * self.V
            cnt = -1
        if directed_acyclic or cycle_detection or topological_sort:
            dag = True
        if euler_tour:
            et = []
        if linked_components:
            lc = []
        if parents or cycle_detection:
            ps = [None] * self.V
        if postorder or topological_sort:
            post = []
        if preorder:
            pre = []
        for s in range(self.V):
            if seen[s]:
                continue
            if bipartite_graph:
                cnt += 1
                bg[s] = (cnt, 0)
            if linked_components:
                lc.append([])
            if parents:
                ps[s] = s
            stack = [(s, 0)] if self.weighted else [s]
            while stack:
                if self.weighted:
                    (x, d) = stack.pop()
                else:
                    x = stack.pop()
                if not seen[x]:
                    seen[x] = True
                    stack.append((x, d) if self.weighted else x)
                    if euler_tour:
                        et.append(x)
                    if linked_components:
                        lc[-1].append(x)
                    if preorder:
                        pre.append(x)
                    for y in self.graph[x]:
                        if self.weighted:
                            (y, d) = y
                        if not seen[y]:
                            stack.append((y, d) if self.weighted else y)
                            if bipartite_graph:
                                bg[y] = (cnt, bg[x][1] ^ 1)
                            if parents or cycle_detection:
                                ps[y] = x
                        elif not finished[y]:
                            if directed_acyclic and dag:
                                dag = False
                                if cycle_detection:
                                    cd = (y, x)
                elif not finished[x]:
                    finished[x] = True
                    if euler_tour:
                        et.append(~x)
                    if postorder or topological_sort:
                        post.append(x)
        if bipartite_graph:
            bg_ = bg
            bg = [[[], []] for i in range(cnt + 1)]
            for tpl in self.edges:
                (i, j) = tpl[:2] if self.weighted else tpl
                if not bg_[i][1] ^ bg_[j][1]:
                    bg[bg_[i][0]] = False
            for x in range(self.V):
                if bg[bg_[x][0]]:
                    bg[bg_[x][0]][bg_[x][1]].append(x)
        tpl = ()
        if bipartite_graph:
            tpl += (bg,)
        if cycle_detection:
            if dag:
                cd = []
            else:
                (y, x) = cd
                cd = self.Route_Restoration(y, x, ps)
            tpl += (cd,)
        if directed_acyclic:
            tpl += (dag,)
        if euler_tour:
            tpl += (et,)
        if linked_components:
            tpl += (lc,)
        if parents:
            tpl += (ps,)
        if postorder:
            tpl += (post,)
        if preorder:
            tpl += (pre,)
        if topological_sort:
            if dag:
                tp_sort = post[::-1]
            else:
                tp_sort = []
            tpl += (tp_sort,)
        if len(tpl) == 1:
            tpl = tpl[0]
        return tpl

    def Tree_Diameter(self, weighted=False):

        def Farthest_Point(u):
            dist = self.SS_BFS(u, weighted_dist=True) if weighted else self.SS_BFS(u, unweighted_dist=True)
            fp = 0
            for i in range(self.V):
                if dist[fp] < dist[i]:
                    fp = i
            return (fp, dist[fp])
        (u, d) = Farthest_Point(0)
        (v, d) = Farthest_Point(u)
        return (u, v, d)

    def SCC(self):
        reverse_graph = [[] for i in range(self.V)]
        for tpl in self.edges:
            (i, j) = tpl[:2] if self.weighted else tpl
            reverse_graph[j].append(i)
        postorder = self.AP_DFS(postorder=True)
        scc = []
        seen = [False] * self.V
        for s in postorder[::-1]:
            if seen[s]:
                continue
            queue = deque([s])
            seen[s] = True
            lst = []
            while queue:
                x = queue.popleft()
                lst.append(x)
                for y in reverse_graph[x]:
                    if self.weighted:
                        y = y[0]
                    if not seen[y]:
                        seen[y] = True
                        queue.append(y)
            scc.append(lst)
        return scc

    def Build_LCA(self, s):
        (self.euler_tour, self.parents, depth) = self.SS_DFS(s, euler_tour=True, parents=True, unweighted_dist=True)
        self.dfs_in_index = [None] * self.V
        self.dfs_out_index = [None] * self.V
        for (i, x) in enumerate(self.euler_tour):
            if x >= 0:
                self.dfs_in_index[x] = i
            else:
                self.dfs_out_index[~x] = i
        self.ST = Segment_Tree(2 * self.V, lambda x, y: min(x, y), float('inf'))
        lst = [None] * 2 * self.V
        for i in range(2 * self.V):
            if self.euler_tour[i] >= 0:
                lst[i] = depth[self.euler_tour[i]]
            else:
                lst[i] = depth[self.parents[~self.euler_tour[i]]]
        self.ST.Build(lst)

    def LCA(self, a, b):
        m = min(self.dfs_in_index[a], self.dfs_in_index[b])
        M = max(self.dfs_in_index[a], self.dfs_in_index[b])
        x = self.euler_tour[self.ST.Fold_Index(m, M + 1)]
        if x >= 0:
            return x
        else:
            return self.parents[~x]

    def Dijkstra(self, s, route_restoration=False):
        dist = [float('inf')] * self.V
        dist[s] = 0
        hq = [(0, s)]
        if route_restoration:
            parents = [None] * self.V
            parents[s] = s
        while hq:
            (dx, x) = heapq.heappop(hq)
            if dist[x] < dx:
                continue
            for (y, dy) in self.graph[x]:
                if dist[y] > dx + dy:
                    dist[y] = dx + dy
                    if route_restoration:
                        parents[y] = x
                    heapq.heappush(hq, (dist[y], y))
        if route_restoration:
            return (dist, parents)
        else:
            return dist

    def Bellman_Ford(self, s, route_restoration=False):
        dist = [float('inf')] * self.V
        dist[s] = 0
        if route_restoration:
            parents = [s] * self.V
        for _ in range(self.V - 1):
            for (i, j, d) in self.edges:
                if dist[j] > dist[i] + d:
                    dist[j] = dist[i] + d
                    if route_restoration:
                        parents[j] = i
                if not self.directed and dist[i] > dist[j] + d:
                    dist[i] = dist[j] + d
                    if route_restoration:
                        parents[i] = j
        negative_cycle = []
        for (i, j, d) in self.edges:
            if dist[j] > dist[i] + d:
                negative_cycle.append(j)
            if not self.directed and dist[i] > dist[j] + d:
                negative_cycle.append(i)
        if negative_cycle:
            is_negative_cycle = [False] * self.V
            for i in negative_cycle:
                if is_negative_cycle[i]:
                    continue
                else:
                    queue = deque([i])
                    is_negative_cycle[i] = True
                    while queue:
                        x = queue.popleft()
                        for (y, d) in self.graph[x]:
                            if not is_negative_cycle[y]:
                                queue.append(y)
                                is_negative_cycle[y] = True
                                if route_restoration:
                                    parents[y] = x
            for i in range(self.V):
                if is_negative_cycle[i]:
                    dist[i] = -float('inf')
        if route_restoration:
            return (dist, parents)
        else:
            return dist

    def Warshall_Floyd(self, route_restoration=False):
        dist = [[float('inf')] * self.V for i in range(self.V)]
        for i in range(self.V):
            dist[i][i] = 0
        if route_restoration:
            parents = [[j for j in range(self.V)] for i in range(self.V)]
        for (i, j, d) in self.edges:
            if dist[i][j] > d:
                dist[i][j] = d
                if route_restoration:
                    parents[i][j] = i
            if not self.directed and dist[j][i] > d:
                dist[j][i] = d
                if route_restoration:
                    parents[j][i] = j
        for k in range(self.V):
            for i in range(self.V):
                for j in range(self.V):
                    if dist[i][j] > dist[i][k] + dist[k][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]
                        if route_restoration:
                            parents[i][j] = parents[k][j]
        for i in range(self.V):
            if dist[i][i] < 0:
                for j in range(self.V):
                    if dist[i][j] != float('inf'):
                        dist[i][j] = -float('inf')
        if route_restoration:
            return (dist, parents)
        else:
            return dist

    def Route_Restoration(self, s, g, parents):
        route = [g]
        while s != g and parents[g] != g:
            g = parents[g]
            route.append(g)
        route = route[::-1]
        return route

    def Kruskal(self):
        UF = UnionFind(self.V)
        sorted_edges = sorted(self.edges, key=lambda x: x[2])
        minimum_spnning_tree = []
        for (i, j, d) in sorted_edges:
            if not UF.Same(i, j):
                UF.Union(i, j)
                minimum_spnning_tree.append((i, j, d))
        return minimum_spnning_tree

    def Ford_Fulkerson(self, s, t):
        max_flow = 0
        residual_graph = [defaultdict(int) for i in range(self.V)]
        if self.weighted:
            for (i, j, d) in self.edges:
                if not d:
                    continue
                residual_graph[i][j] += d
                if not self.directed:
                    residual_graph[j][i] += d
        else:
            for (i, j) in self.edges:
                residual_graph[i][j] += 1
                if not self.directed:
                    residual_graph[j][i] += 1
        while True:
            parents = [None] * self.V
            parents[s] = s
            seen = [False] * self.V
            seen[s] = True
            queue = deque([s])
            while queue:
                x = queue.popleft()
                for y in residual_graph[x].keys():
                    if not seen[y]:
                        seen[y] = True
                        queue.append(y)
                        parents[y] = x
                        if y == t:
                            tt = t
                            while tt != s:
                                residual_graph[parents[tt]][tt] -= 1
                                residual_graph[tt][parents[tt]] += 1
                                if not residual_graph[parents[tt]][tt]:
                                    residual_graph[parents[tt]].pop(tt)
                                tt = parents[tt]
                            max_flow += 1
                            break
                else:
                    continue
                break
            else:
                break
        return max_flow

    def BFS(self, s):
        seen = [False] * self.V
        seen[s] = True
        queue = deque([s])
        while queue:
            x = queue.popleft()
            for y in self.graph[x]:
                if self.weighted:
                    (y, d) = y
                if not seen[y]:
                    seen[y] = True
                    queue.append(y)
        return

    def DFS(self, s):
        seen = [False] * self.V
        finished = [False] * self.V
        stack = [(s, 0)] if self.weighted else [s]
        while stack:
            if self.weighted:
                (x, d) = stack.pop()
            else:
                x = stack.pop()
            if not seen[x]:
                seen[x] = True
                stack.append((x, d) if self.weighted else x)
                for y in self.graph[x]:
                    if self.weighted:
                        (y, d) = y
                    if not seen[y]:
                        stack.append((y, d) if self.weighted else y)
            elif not finished[x]:
                finished[x] = True
        return
N = int(readline())
A = list(map(int, readline().split()))
edges = []
for i in range(N - 1):
    (u, v) = map(int, readline().split())
    u -= 1
    v -= 1
    edges.append((u, v))
G = Graph(N, edges=edges)
ans = 0
cnt0 = [[0] * 20 for a in A]
cnt1 = [[0] * 20 for a in A]
parents = G.SS_DFS(0, parents=True)
for x in G.SS_DFS(0, postorder=True):
    for i in range(20):
        for y in G.graph[x]:
            if y == parents[x]:
                continue
            cnt0[x][i] += cnt0[y][i]
            cnt1[x][i] += cnt1[y][i]
        if A[x] >> i & 1:
            ans += cnt0[x][i] * (cnt0[x][i] + 1) // 2 << i
            ans += cnt1[x][i] * (cnt1[x][i] - 1) // 2 << i
            ans += 1 << i
            for y in G.graph[x]:
                if y == parents[x]:
                    continue
                ans -= cnt0[y][i] * (cnt0[y][i] - 1) // 2 << i
                ans -= cnt1[y][i] * (cnt1[y][i] - 1) // 2 << i
            (cnt0[x][i], cnt1[x][i]) = (cnt1[x][i], cnt0[x][i])
            cnt1[x][i] += 1
        else:
            ans += (cnt0[x][i] + 1) * cnt1[x][i] << i
            for y in G.graph[x]:
                if y == parents[x]:
                    continue
                ans -= cnt0[y][i] * cnt1[y][i] << i
            cnt0[x][i] += 1
print(ans)