Problem
Dasha có n người bạn, mỗi người có i quả táo. Tất cả bạn bè tạo thành các công ty không chồng chéo. Bất cứ lúc nào, hai công ty có thể hợp nhất. Dasha cẩn thận ghi nhớ tất cả các hành động của bạn bè. Bây giờ cô ấy muốn biết có bao nhiêu quả táo trong mỗi công ty mới thành lập. Ban đầu, tất cả bạn bè đi chơi riêng, tức là không có công ty nào có nhiều hơn một người. Dasha không có táo và cô ấy không tham gia vào các hiệp hội.
Đầu vào:
Dòng đầu tiên chứa các số nguyên n và k ( 2 <= n <= 300000, 0 <= k <= n - 1 ) - số lượng bạn bè của Dasha và số lượng sự kiện. Dòng thứ hai chứa n số - ai (0 <= ai <= 10^9) - số táo mà người bạn thứ i của Dasha có. K dòng tiếp theo chứa hai số u, v ( 1 <= u, v <= n). Sự kiện (u, v) có nghĩa là công ty với người bạn thứ u của Dasha đã gia nhập công ty với người bạn thứ v.
Đầu ra:
Đối với mỗi k truy vấn in ra số lượng táo trong công ty mới.
|
Nhập |
Đầu ra |
|
3 2
|
3
6
|
|
2 1
999999999 0
1 2
|
999999999 |
(c) Ibrahim Ahmad, 2018