e128. P-8-7. 寶石的顏色 (108 全國高中賽)

Content

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

Time limit: 1 秒

Input

第一行有是一個正整數 n， n <= 2e5，代表地圖上有 n 個站。第二行是 n 個非負整數，依序代表每一站的寶石顏色號碼 c(0), c(1), …, c(n – 1)；寶石的顏色號碼不超過 1e9。接著有 n–1 行，每行兩個以空白間隔的整數 s 與 t，表示有一條 s 到 t 的道路。

Output

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

Sample Input

範例一：
6
0 0 0 0 0 0
0 1
1 2
0 3
1 4
1 5

範例二：
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

Sample Output

範例一：
3

範例二：
2

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (20%): 1.0s , <1M
公開測資點#1 (20%): 1.0s , <10M
公開測資點#2 (20%): 1.0s , <10M
公開測資點#3 (20%): 1.0s , <10M
公開測資點#4 (20%): 1.0s , <10M

Hint ：

(測資檔案中，第一筆測資只有一色，第二筆測資不超過 10 個顏色)

Tags:

DFS 樹

出處:

AP325 [管理者：

mcjksieu005 (mcjksieu005)

]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」