题目描述

小 Y 的果园里有一棵以 $1$ 号节点为根的树，共 $n$ 个节点。为了夜里巡逻，他要在树上架设若干盏路灯。

在第 $i$ 个节点架设一盏路灯需要花费 $c_i$ 的经费。一盏路灯装好以后，它所在的节点以及与它直接相连的所有节点都会被照亮。

小 Y 希望每个节点都被照亮，请你求出所需的最少经费。

注意：只有架设了路灯的节点才会照亮别人，被照亮并不会让路灯"传染"出去。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $c_1\sim c_n$。

接下来 $n-1$ 行，每行两个整数 $u,v$，表示一条连接 $u$ 与 $v$ 的边。

输出格式

一行一个整数，表示最少经费。

输入输出样例 #1

输入 #1

3
5 1 5
1 2
2 3

输出 #1

1

说明

【样例解释】

只在 $2$ 号节点架设一盏路灯，花费 $1$，即可照亮 $1,2,3$ 三个节点，显然这是最优的。

【数据范围】

数据范围

• 对于 $100\%$ 的数据，$1\le n\le 5000$，$1\le c_i\le 10^4$。