سیب
Problem
داشا n دوست دارد، هر کدام یک i سیب دارند. همه دوستان شرکت های غیر همپوشانی تشکیل می دهند. در هر زمان، دو شرکت می توانند ادغام شوند. داشا با دقت تمام اقدامات دوستانش را به یاد آورد. اکنون او علاقه مند است که بداند در هر شرکت تازه تأسیس چند سیب وجود دارد. در ابتدا، همه دوستان به طور جداگانه پاتوق می کنند، یعنی. هیچ شرکتی وجود ندارد که در آن بیش از یک نفر وجود داشته باشد. داشا سیب ندارد و در انجمن ها شرکت نمی کند.
ورودی:
خط اول شامل اعداد صحیح n و k ( 2 <= n <= 300000، 0 <= k <= n - 1 ) - تعداد دوستان داشا و تعداد رویدادها. خط دوم شامل n عدد است - ai (0 <= ai <= 10^9) - تعداد سیب هایی که دوست i-ام داشا دارد. k خطوط بعدی شامل دو عدد u, v ( 1 <= u, v <= n) است. رویداد (u, v) به این معنی است که شرکت با دوست u-ام داشا با دوست v به شرکت ملحق شده است.
خروجی:
برای هر یک از k پرس و جو تعداد سیب های موجود در شرکت جدید را چاپ کنید.
<بدن>
|
وارد کنید |
خروجی |
|
3 2
|
3
6
|
|
2 1
999999999 0
1 2
|
999999999 |
(ج) ابراهیم احمد، 2018