開車蒐集寶物 (AP325 P-7-2)

參加一個蒐集寶物的遊戲，你拿到一個地圖，地圖上有 \(n\) 個藏寶點，每個藏寶點有若干價值的寶物，由於你的團隊是最頂尖的，只要能到達藏寶點一定可以取得該藏寶點的寶藏。從地圖上看得到一共有 \(m\) 條道路，每條道路連接兩個藏寶點，而且每條道路都是雙向可以通行的。在遊戲的一開始，你可以要求直升機將你的團隊運送到某個藏寶點，而且你可以獲得一部車與充足的油料，但是直升機的載送只有一次，所以你必須決定要從哪裡開始才可以獲得最多的寶藏總價值。

輸入格式

第一行是兩個正整數 \(n\) 與 \(m\)，代表藏寶地點數與道路數，地點是以 \(0 \sim n-1\) 編號；第二行有 \(n\) 個非負整數，依序是每一個地點的寶藏價值；接下來有 \(m\) 行，每一行兩個整數 \(a\) 與 \(b\)，代表一條道路連接的兩個地點編號。

限制

• \(1 \le n \le 5 \times 10^4\)。
• \(1 \le m \le 5 \times 10^5\)。
• 每個地點的寶藏價值是不超過 \(100\) 的非負整數。
• \(0 \le a, b \le n-1\)；兩點之間可能有多條道路，有些道路的兩端點可能是同一地點。

輸出格式

輸出最大可以獲得的寶藏總價值。

評分說明

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

範例輸入 1

7 6
5 2 4 2 1 1 8
5 1
1 3
1 4
2 0
2 0
3 3

範例輸出 1

9

範例輸入 2

3 2
2 1 5
1 0
0 1

範例輸出 2

5

範例說明

範例一：降落在 \(0\) 可以獲得 \(0\) 與 \(2\) 的寶藏，價值為 \(5 + 4 = 9\)。

範例二：降落在 \(2\) 可獲得價值 \(5\)。

題目來源

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