佔領連續的城鎮 (AP325 Q-8-12)

某個遊戲中有 \(n\) 個城鎮以 \(1 \sim n\) 編號，這些城鎮以 \(n-1\) 條道路連接，每條道路都是雙向通行且連接兩個不同的城鎮，已知從任兩個城鎮之間都可以經由這些道路通達。現在你要佔領一些城鎮來獲取最大的利益，佔領編號 \(i\) 的城鎮可以獲得 \(w[i]\) 的利益（利益可能是負的），但是你佔領的城鎮必須內部可以互相通達，也就是說，若 \(i\) 與 \(j\) 都是你的領地，則從 \(i\) 出發可以只經過你自己的城鎮到達 \(j\)。你也可以一個城鎮都不佔領，此時總利益為 \(0\)。請計算你最多可以獲得多少總和利益。

輸入格式

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

限制

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

輸出格式

最多可以獲得的總和利益。

評分說明

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

範例輸入 1

5
-2 3 -1 3 -4
1 2
5 1
5 3
5 4

範例輸出 1

3

範例輸入 2

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

範例輸出 2

7

範例說明

範例一：選 \(\{2\}\) 或 \(\{4\}\) 都是 \(3\)。

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

題目來源

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