a135.
P_8_13 不同成本的購物中心 (@@)
Content
有 $n$ 個小村鎮以 $1 \sim n$ 編號，這些村鎮以 $n-1$ 條道路連接，每條道路都是雙向通行且連接兩個不同的村鎮，已知從任兩個村莊之間都可以經由這些道路通達，兩個村莊稱為鄰近的村莊，如果它們之間有一條道路直接相連。
現在要選一些村莊成立服務中心，因為預算的關係無法每個村莊都成立一個服務中心，政府的政策決定：如果某個村莊沒有設服務中心，那麼他一定有一個鄰近的村莊有服務中心。也就是說，任何一個村莊最多只要經過一條道路就可以到達一個有設服務中心的村莊。每個村莊設立服務中心的成本不同，在編號 $i$ 的村莊成立服務中心需要的成本是 $w_i$，我們希望以最少的總成本設置服務中心，請你計算最少的總成本。
Input
第一行是正整數 $n$，$n>1$，村莊以 $1 \sim n$ 編號。
第二行有 $n$ 個正整數，依序是 $w_1, w_2, … , w_n$。
接下來有 $n-1$ 行是道路的資料，每一行有兩個正整數 $u$ 與 $v$，代表有一條道路連接 $u$ 與 $v$。
$n$ 不超過 $10^5$，每個村莊設置成本不超過 $1000$。
Output
輸出需要成立服務中心的最少總成本
Sample Input
#1
5 2 4 1 3 7 1 2 5 1 5 3 5 4
Sample Output
#1
6
Sample Input
#2
7 1 3 3 1 2 2 1 1 2 2 3 4 3 5 4 5 6 7 6
Sample Output
#2
3
測資資訊：
記憶體限制：
512
MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1K
公開 測資點#2 (20%): 1.0s , <10M
公開 測資點#3 (20%): 1.0s , <10M
公開 測資點#4 (20%): 1.0s , <10M
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1K
公開 測資點#2 (20%): 1.0s , <10M
公開 測資點#3 (20%): 1.0s , <10M
公開 測資點#4 (20%): 1.0s , <10M
Hint ：
範例一說明：設在 ${1,3,4}$ 成本 $6$。
範例二說明：這是 $7$ 個點排成一條路徑，每個點成本皆相同。選 ${1,4,7}$ 成本是 $3$。
Tags:
| ID | User | Problem | Subject | Hit | Post Date |
| 1 |
|
a135 | 92 | 2024-06-02 22:02 |