內容
某座國家級森林公園內共有 N（1≤N≤200000）個生態據點，編號為 1 至 N。這些據點之間由 N−1 條雙向步道相連，且任意兩個據點之間都恰好存在一條簡單路徑，意即整座森林的據點與步道結構形成一棵樹狀圖（Tree）。
為了保護森林資源並防範森林火災，林管處計畫在某些據點設立「巡守站」 。在第 i 個據點設置巡守站需要投入建造成本 Ci（1≤Ci≤109）。一座巡守站的守備範圍包含該據點本身，以及所有與該據點直接相連的相鄰據點。
在一個 N=5 的範例中，覆蓋所有據點的最佳建設策略為選定1號與2號據點設立巡守站。此組合的總建造成本為5，為所有可行方案中的花費最小值。
請你寫一個程式，協助林管處挑選出若干個據點設立巡守站，使得森林中的每一個據點都至少被一座巡守站看守到，且在滿足此條件的前提下，計算出所需的最小總建造成本。
輸入說明
第一行包含一個正整數 N，代表生態據點的總數。
第二行包含 N 個正整數 C1, C2, …, Cn，依序代表在各個據點設置巡守站的建造成本。
接下來的 N−1 行，每行包含兩個正整數 u 與 v（1≤u,v≤N），代表據點 u 與據點 v 之間有一條雙向步道相連。
輸出說明
請輸出一個整數，代表能讓所有據點皆受到巡守的最小總建造成本。
範例輸入
#1
5 3 2 4 6 1 1 2 1 3 2 4 2 5
範例輸出
#1
5
範例輸入
#2
7 100 1 1 10 10 10 10 1 2 1 3 2 4 2 5 3 6 3 7
範例輸出
#2
2
測資資訊：
記憶體限制：
64
MB
不公開 測資點#0 (5%): 1.0s , <10M
不公開 測資點#1 (5%): 1.0s , <10M
不公開 測資點#2 (5%): 1.0s , <10M
不公開 測資點#3 (5%): 1.0s , <10M
不公開 測資點#4 (5%): 1.0s , <10M
不公開 測資點#5 (5%): 1.0s , <10M
不公開 測資點#6 (5%): 1.0s , <10M
不公開 測資點#7 (5%): 1.0s , <10M
不公開 測資點#8 (5%): 1.0s , <10M
不公開 測資點#9 (5%): 1.0s , <10M
不公開 測資點#10 (5%): 1.0s , <10M
不公開 測資點#11 (5%): 1.0s , <10M
不公開 測資點#12 (5%): 1.0s , <1M
不公開 測資點#13 (5%): 1.0s , <1M
不公開 測資點#14 (5%): 1.0s , <1M
不公開 測資點#15 (5%): 1.0s , <1M
不公開 測資點#16 (5%): 1.0s , <1K
不公開 測資點#17 (5%): 1.0s , <1K
不公開 測資點#18 (5%): 1.0s , <1K
不公開 測資點#19 (5%): 1.0s , <1K
不公開 測資點#0 (5%): 1.0s , <10M
不公開 測資點#1 (5%): 1.0s , <10M
不公開 測資點#2 (5%): 1.0s , <10M
不公開 測資點#3 (5%): 1.0s , <10M
不公開 測資點#4 (5%): 1.0s , <10M
不公開 測資點#5 (5%): 1.0s , <10M
不公開 測資點#6 (5%): 1.0s , <10M
不公開 測資點#7 (5%): 1.0s , <10M
不公開 測資點#8 (5%): 1.0s , <10M
不公開 測資點#9 (5%): 1.0s , <10M
不公開 測資點#10 (5%): 1.0s , <10M
不公開 測資點#11 (5%): 1.0s , <10M
不公開 測資點#12 (5%): 1.0s , <1M
不公開 測資點#13 (5%): 1.0s , <1M
不公開 測資點#14 (5%): 1.0s , <1M
不公開 測資點#15 (5%): 1.0s , <1M
不公開 測資點#16 (5%): 1.0s , <1K
不公開 測資點#17 (5%): 1.0s , <1K
不公開 測資點#18 (5%): 1.0s , <1K
不公開 測資點#19 (5%): 1.0s , <1K
提示 ：
標籤:
出處:
[管理者：
lsstmoonis@g
...
(CERE)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||