有n個小村鎮以1~n編號，這些村鎮以n-1條道路連接，每條道路都是雙向通行且連接兩個不同的村鎮，已知從任兩個村莊之間都可以經由這些道路通達，兩個村莊稱為鄰近的村莊，如果它們之間有一條道路直接相連。現在要選一些村莊成立服務中心，因為預算的關係無法每個村莊都成立一個服務中心，政府的政策決定：如果某個村莊沒有設服務中心，那麼他一定有一個鄰近的村莊有服務中心。也就是說，任何一個村莊最多只要經過一條道路就可以到達一個有設服務中心的村莊。每個村莊設立服務中心的成本不同，在編號i的村莊成立服務中心需要的成本是w[i]，我們希望以最少的總成本設置服務中心，請你計算最少的總成本。
第一行是正整數n，n>1，村莊以1~n編號。第二行有n個正整數，依序是w[1],w[2],…,w[n]。接下來有n-1行是道路的資料，每一行有兩個正整數u與v，代表有一條道路連接u與v。n不超過1e5，每個村莊設置成本不超過1000。
需要成立服務中心的最少總成本。
5 2 4 1 3 7 1 2 5 1 5 3 5 4
6
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||