题解

题面描述
在一棵以节点 $1$ 为根的树上，共有 $n$ 个节点，每个节点 $i$ 初始权值为 $a_i$。小红可以进行如下操作：

• 选择任意节点 $v$ 和一个非负整数 $x$，
• 对节点 $v$ 的子树中所有与 $v$ 的距离为偶数的节点 $u$，执行$$a_u \gets a_u \oplus x\,$$
• 操作的代价为 $x$。

问：最少需要多少总代价，才能将所有节点的权值都变为 $0$？

题目内容

在神秘莫测的比特王国中，流传着这样一个传说—在王国深处生长着一棵蕴含天机的神奇大树。这棵树由$n$个节点构成,$1$号点是根节点，

每个节点都记录着一段古老的符文，初始每个节点的符文为$a_i$。传说只有将树上所有节点的符文调和为零，才能开启通往失落宝藏的大门，聪明勇敢的小红接受了挑战，她掌握了一套奇特的操作法则，能够对树中部分节点施法改变其符文，但每次施法都需要付出一定代价,

具体来说，小红可以进行如下操作:

• 选择树中的任一节点$v$及一个非负整数$x$。
• 将$v$ 以及$v$的子树中所有与$v$距离为偶数的节点的权值进行异或操作，即更新为:$a[u]=a[u]\oplus x$
• 每进行一次此操作就产生的代价。

请问小红至少需要花费多少总代价，才能使得所有节点的符文权值均变为$0$?

名词解释

在一棵树中,对于任一节点$v$，以$v$为根节点并包含所有从出发可以达到的后代节点(包括$v$自身)的集合构成了$v$的子树。

在树中，任意两个节点之间仅存在一条简单路径，该路径上所经过的边的数目定义为这两个节点之间的距离。

输入描述

第一行包含一个整数$n$，表示节点的数量.

第二行包含$n$个整数$a_1,a_2,...an$，表示各节点的初始权值。

接下来$n-1$行,每行包含两个整数$u$和$v$，表示树中一你边。所始边构成一棵以$1$为根的树。

$1≤n≤2×10^5$

$0≦a≦10^9$

输出描述

输出一个整数，表示将所有节点的权值变为$0$所需的最小总代价.

样例1

输入

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

输出

9

说明

先选择节点$1$，花费$1$的代价进行操作，操作后节点权值变为$[0,4,2,5,5]$

再选择节点$2$，花费$4$的代价进行操作，操作后节点权值变为$[0,0,2,1,1]$

再选择节点$3$，花费$2$的代价进行操作，操作后节点权值变为$[0,0,0,1,1]$

再选择节点$4$，花费$1$的代价进行操作，操作后节点权值变为$[0,0,0,0,1]$

最后选择节点$5$，花费$1$的代价进行操作，操作后节点权值变为$[0,0,0,0,0]$

总花费为$1+4+2+1+1=9$