题目描述

给定一棵有 $n$ 个结点的无根树，树根固定为 $1$ 号点，每个结点带有一个权值。定义一棵子树的和为该子树内所有结点权值相加。求以每个结点为根的子树总和，最后只输出根节点（1号）对应的子树总和。

输入描述

第一行一个整数 $n$，代表树上节点总数； 第二行 $n$ 个整数，依次为 $1\sim n$ 每个节点的权值； 接下来 $n-1$ 行，每行两个整数 $u,v$，代表 $u$ 与 $v$ 之间连一条边。

输出描述

输出一行一个整数，表示整棵树（根1）的子树权值总和。

输入样例

3
2 5 3
1 2
1 3

输出样例

10

数据范围

$1 \le n \le 1000$，单个节点权值 $1\le val \le 100$