CF1637F Towers

给定一棵有 $n$ 个顶点的树，顶点编号为 $1$ 到 $n$。第 $i$ 个顶点的高度为 $h_i$。你可以在任意顶点放置任意数量的信号塔，对于每个信号塔，你可以选择放在哪个顶点，并且可以选择它的效率。设置一个效率为 $e$ 的信号塔需要花费 $e$ 个金币，其中 $e > 0$。 如果存在一对分别位于顶点 $u$ 和 $v$ 的信号塔（$u \neq v$，但允许 $x = u$ 或 $x = v$），它们的效率分别为 $e_u$ 和 $e_v$，并且满足 $\min(e_u, e_v) \geq h_x$，且顶点 $x$ 位于 $u$ 和 $v$ 的路径上，则认为顶点 $x$ 能够接收到信号。 请你求出，为了让所有顶点都能接收到信号，所需的最小金币数。

第一行包含一个整数 $n$（$2 \le n \le 200\,000$），表示树的顶点数。 第二行包含 $n$ 个整数 $h_i$（$1 \le h_i \le 10^9$），表示每个顶点的高度。 接下来的 $n-1$ 行，每行包含两个整数 $v_i, u_i$（$1 \le v_i, u_i \le n$），表示树中的一条边。保证给定的边构成一棵树。

输出一个整数，表示所需的最小金币数。

在第一个测试用例中，最优方案是在顶点 $1$ 和 $3$ 各安装一个效率为 $2$ 的信号塔。 在第二个测试用例中，最优方案是在顶点 $1$ 安装一个效率为 $1$ 的信号塔，在顶点 $2$ 和 $5$ 各安装一个效率为 $3$ 的信号塔。 在第三个测试用例中，最优方案是在顶点 $1$ 和 $2$ 各安装一个效率为 $6$ 的信号塔。 由 ChatGPT 4.1 翻译