#F6. 皇宫守卫

皇宫守卫

T2 皇宫守卫(guard)

时间限制:1.0 秒 空间限制:256 MB

题目描述

皇宫可以看作一棵有 nn 个房间的树,房间编号为 1,2,…,n1,2,\dots,n,房间之间共有 n−1n-1 条走廊。为了保护皇宫,国王决定在一些房间里安排守卫。

在第 ii 个房间安排一名守卫需要花费 cic_i 的代价。一名守卫可以保护他所在的房间,以及所有与这个房间直接相连的房间。一个房间可以安排多名守卫,但显然不会更优。

请你求出保护所有房间所需的最小总代价。

输入格式

第一行一个正整数 nn。

第二行 nn 个正整数 c1,c2,…,cnc_1,c_2,\dots,c_n。

接下来 n−1n-1 行,每行两个正整数 u,vu,v,表示房间 uu 和房间 vv 之间有一条走廊。

输出格式

输出一行一个整数,表示最小总代价。

样例 1

输入:

3
5 1 5
1 2
2 3

输出:

1

样例 1 解释: 只在 22 号房间安排一名守卫,他可以保护 1,2,31,2,3 号房间,总代价为 11。

样例 2

输入:

4
10 1 1 1
1 2
1 3
1 4

输出:

3

样例 2 解释: 在 2,3,42,3,4 号房间各安排一名守卫,总代价为 33;若只在 11 号房间安排守卫则需要代价 1010,因此最优答案为 33。

数据范围

对于全部测试数据:1≤n≤2×1051\le n\le 2\times 10^5;1≤ci≤1091\le c_i\le 10^9;保证输入给出的是一个 nn 个点的树。

子任务

子任务 分值 特殊限制
1 20 n≤20n\le 20
2 树是一条链
3 树是一个菊花(11 号点与其余所有点相邻)
4 40 无特殊限制

提示: 答案可能超过 231−12^{31}-1,请使用 6464 位整数。