不同成本的購物中心 (AP325 P-8-13)

有 \(n\) 個小村鎮以 \(1 \sim n\) 編號，這些村鎮以 \(n-1\) 條道路連接，每條道路都是雙向通行且連接兩個不同的村鎮，已知從任兩個村莊之間都可以經由這些道路通達。兩個村莊稱為鄰近的村莊，如果它們之間有一條道路直接相連。現在要選一些村莊成立服務中心，因為預算的關係無法每個村莊都成立一個服務中心，政府的政策決定：如果某個村莊沒有設服務中心，那麼它一定有一個鄰近的村莊有服務中心。也就是說，任何一個村莊最多只要經過一條道路就可以到達一個有設服務中心的村莊。每個村莊設立服務中心的成本不同，在編號 \(i\) 的村莊成立服務中心需要的成本是 \(w[i]\)，我們希望以最少的總成本設置服務中心，請你計算最少的總成本。

輸入格式

第一行是正整數 \(n\)，村莊以 \(1 \sim n\) 編號。第二行有 \(n\) 個正整數，依序是 \(w[1], w[2], \ldots, w[n]\)。接下來有 \(n-1\) 行是道路的資料，每一行有兩個正整數 \(u\) 與 \(v\)，代表有一條道路連接 \(u\) 與 \(v\)。同一行的數字以一個空白隔開。

限制

• \(2 \le n \le 10^5\)。
• \(1 \le w[i] \le 1000\)。
• \(1 \le u, v \le n\)，\(u \ne v\)；保證任兩個村莊之間都可以經由道路互相到達。

輸出格式

需要成立服務中心的最少總成本。

評分說明

每筆計分測資獨立計分，每筆 5 分，共 100 分；範例不計分。

範例輸入 1

5
2 4 1 3 7
1 2
5 1
5 3
5 4

範例輸出 1

6

範例輸入 2

7
1 3 3 1 2 2 1
1 2
2 3
4 3
5 4
5 6
7 6

範例輸出 2

3

範例說明

範例一：設在 \(\{1, 3, 4\}\)，成本 \(6\)。

範例二：這是 \(7\) 個點排成一條路徑，選 \(\{1, 4, 7\}\)，成本是 \(3\)。

題目來源

本題出自中正大學吳邦一教授所著《AP325－從 APCS 實作題檢測三級到五級》（v1.5）第 8 章 P-8-13，第 304 頁；經作者同意於 AACPOJ 免費公開。教材下載：AP325 講義（Google Drive）；Python 版：AP325-Python（HackMD）。