题目描述

给定一棵$n$个点树，其中点$1$为根节点，并且根为第0层。树中每个点都有一个权值，现在让你求出树中所有奇数层的点的权值之和。

注意：层是每个点到根节点的最短边数，根为第0层。

输入格式

第一行一个整数$n$。

第二行包含$n$个正整数$a_1, a_2, . . . , a_n（1 ≤ a_i ≤ 10^9）$，表示编号为$i$的节点点权。

接下来$n - 1$行每行两个整数$u, v$。代表$u$与$v$之间有一条边。

输出格式

输出所有奇数层节点的权值之和

样例

5
5 15 1 4 9
1 2
1 3
2 4
2 5

16

数据范围

$1 \le n \le 10^{5}$

$1 ≤ a_i ≤ 10^9$

$1 \le u, v \le n$