Tower

【题目描述】

给你一颗树，每个点有一个高度 $h_{i}$，你可以放置任意个塔在节点上，每个塔都有一个效率 $e$，搭建一个效率为 $e$ 的塔需要消耗 $e$ 个金币。对于任意一个节点能够收到塔信号的充要条件是，存在两个点 $u, v$，使得当前节点 $x$ 在 $u, v$ 的路径上且 $\min(e_{u}, e_{v}) \ge h_{x}$。

现在你需要在保证所有节点都能接收到信号的情况下，求出最小花费。

【输入格式】

从文件 tower.in 中读取数据

第一行一个正整数 $n(2 \leq n \leq 2 \times 10^5)$ 表示节点数。

接下来一行 $n$ 个正整数 $h_{i}(1 \leq h_{i} \leq 10^9)$ 表示第 $i$ 个节点的高度。

接下来 $n-1$ 行每行两个正整数 $u_{i}, v_{i}(1 \leq u_{i}, v_{i} \leq n)$ 表示树的一条边。

【输出格式】

输出到文件 tower.out 中

一行一个整数表示最小花费。

【输入样例】

3
1 2 1
1 2
2 3

【输出样例】

4

【数据范围与约定】

• 对于前 $15\%$ 的数据：$n \leq 10$
• 另有 $25\%$ 的数据：$h_{i} = 1$
• 另有 $10\%$ 的数据：给出的是一条链
• 对于 $100\%$ 的数据，没有特殊限制。

【样例解释】

在 $1, 3$ 节点放上效率为 $2$ 的塔。