某個遊戲中有 $n$ 個城鎮以 $1 \sim n$ 編號，這些城鎮以 $n-1$ 條道路連接，每條道路都是雙向通行且連接兩個不同的城鎮，已知從任兩個城鎮之間都可以經由這些道路通達。現在你要佔領一些城鎮來獲取最大的利益，佔領編號 $i$ 的城鎮可以獲得 $w_i$ 的利益， 但是你佔領的城鎮必須內部可以互相通達，也就是說，若 $i$ 與 $j$ 都是你的領地，則從 $i$ 出發可以只經過你自己的城鎮到達 $j$。請計算你最多可以獲得多少總和利益。
第一行是正整數 $n$，$n>1$，村莊以 $1\sim n$ 編號。
第二行有 $n$ 個整數，依序是 $w_1,w_2, \dots ,w_n$。
接下來有 $n-1$ 行是道路的資料，每一行有兩個正整數 $u$ 與 $v$，代表有一條道路連接 $u$ 與 $v$。
$n$ 不超過 $10^5$，每個城鎮利益的絕對值不超過 $10^4$。
最多可以獲得的總和利益。
5 -2 3 -1 3 -4 1 2 5 1 5 3 5 4
3
7 2 -1 4 -3 5 -3 2 1 2 2 3 4 3 5 4 5 6 7 6
7
範例一說明：選 {2} 或 {4} 都是 3。
範例二說明：這是 7 個點排成一條路徑，選 {1,2,3,4,5}，總和是 7。
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||