U380756 【搬运】Loser and Router

模拟赛 Day 1 T2

有一个 Loser 叫做 小 N，他现在要解决一个问题： 有一棵 $n$ 个点的树，每个节点有一个代价 $a_i$。 你需要选择一些点，使得每个点 $i(1\leq i\leq n)$ 满足以下条件中至少一个： - 第 $i$ 个点被选中。 - 与第 $i$ 个点距离不超过 $1$ 的某个点被选中。 你当然需要帮这个 Loser 求出最小代价，这样你才能成为 Winner。

$n$ $a_1,a_2,...a_n$ $u\ v$ 代表边

最小代价

$n\leq 10^6,a_i\leq10^9$