寶石的顏色 (AP325 P-8-7)

尋寶之旅的遊戲有一個地圖，地圖上有 \(n\) 個站，以 \(0\) 到 \(n-1\) 編號，此外有 \(n-1\) 條道路，這些道路都是單向的，遊戲固定從 \(0\) 號站出發，且已知從 \(0\) 號站出發可以直接或間接到達任何其他站。每一個站都有一顆寶石，寶石有分為多種顏色，第 \(i\) 站存放的寶石顏色為 \(c(i)\)。出發之前，你可以選定一種顏色的寶石收集箱，路途中遇到與你的收集箱相同顏色的寶石就可以收集（包含起點），請你計算最多可以收集到多少顆同色寶石。

輸入格式

第一行是一個正整數 \(n\)，代表地圖上有 \(n\) 個站。第二行是 \(n\) 個非負整數，依序代表每一站的寶石顏色號碼 \(c(0), c(1), \ldots, c(n-1)\)。接著有 \(n-1\) 行，每行兩個以空白間隔的整數 \(s\) 與 \(t\)，表示有一條 \(s\) 到 \(t\) 的道路。

限制

• \(1 \le n \le 2 \times 10^5\)。
• \(0 \le c(i) \le 10^9\)。
• \(0 \le s, t \le n-1\)，\(s \ne t\)；保證從 \(0\) 號站可以到達每一站。

輸出格式

輸出為一整數，代表最多可能收集到的寶石數量。

評分說明

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

範例輸入 1

6
0 0 0 0 0 0
0 1
1 2
0 3
1 4
1 5

範例輸出 1

3

範例輸入 2

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

範例輸出 2

2

題目來源

本題出自中正大學吳邦一教授所著《AP325－從 APCS 實作題檢測三級到五級》（v1.5）第 8 章 P-8-7，第 292 頁；經作者同意於 AACPOJ 免費公開。教材下載：AP325 講義（Google Drive）；Python 版：AP325-Python（HackMD）。原題出自 108 學年度全國高級中等學校資訊學科能力競賽（教材標註「108 全國高中賽」）。