建造堡壘 (APCS 2026-11 高級)

有一個古老的國家共有 \(n\) 個城市，編號為 \(1\) 到 \(n\)。城市之間有 \(n-1\) 條雙向道路，每條道路連接兩個不同的城市，而且任兩個城市都可以經由道路互相到達。

為了抵禦外敵，國王打算在一些城市建造堡壘，在城市 \(i\) 建造堡壘的花費是 \(C_i\)。國王要求每一條道路連接的兩個城市中，至少要有一個城市建有堡壘。請問最少需要花費多少？

下圖是範例 1 的國家，圓圈裡的數字是城市編號，圓圈下方小方框裡的數字是在這個城市建造堡壘的花費。

輸入格式

第一行有一個整數 \(n\)，代表城市的數量。

第二行有 \(n\) 個整數 \(C_1, C_2, \ldots, C_n\)，依序代表在城市 \(1\) 到城市 \(n\) 建造堡壘的花費。

接下來有 \(n-1\) 行，每行有兩個整數 \(u, v\)，代表城市 \(u\) 與城市 \(v\) 之間有一條道路。

限制

• \(2 \le n \le 2 \times 10^5\)
• \(0 \le C_i \le 10^4\)
• \(1 \le u, v \le n\)，\(u \ne v\)
• 任兩個城市都可以經由道路互相到達。

輸出格式

輸出一個整數，代表最少需要的總花費。

評分說明

每一筆測試資料的執行時間限制均為 \(2\) 秒，依正確通過的測試資料筆數給分。

範例輸入 1

7
4 5 3 9 3 0 2
2 5
1 2
6 2
6 4
4 7
3 4

範例輸出 1

10

範例解釋 1

在城市 \(2\)、\(3\)、\(6\)、\(7\) 建造堡壘（下圖中塗滿顏色的城市），總花費是 \(5 + 3 + 0 + 2 = 10\)。每一條道路都至少有一端建有堡壘，而且沒有花費更少的建法。

如果只在城市 \(2\)、\(4\) 建造堡壘，也能讓每一條道路都至少有一端建有堡壘，但花費是 \(5 + 9 = 14\)，比較多。

範例輸入 2

6
1 2 4 1 8 2
5 1
2 4
6 3
2 5
1 6

範例輸出 2

5

範例解釋 2

這些道路把 \(6\) 個城市連成一條線，依序是城市 \(3\)、\(6\)、\(1\)、\(5\)、\(2\)、\(4\)。在城市 \(6\)、\(1\)、\(2\) 建造堡壘，花費是 \(2 + 1 + 2 = 5\)，這就是最少的花費。城市 \(6\) 與城市 \(1\) 之間這條道路的兩端都建了堡壘，這也是允許的。

題目來源

APCS 2026 年 11 月高級實作題第 1 題。

官方未公布題本，題敘依考生考後回憶整理，細節可能與正式試題有出入。