لدى داشا أصدقاء ، كل منهم لديه تفاحة
i . جميع الأصدقاء يشكلون شركات غير متداخلة. يمكن دمج شركتين في أي وقت. تذكرت داشا بعناية كل تصرفات صديقاتها. وهي الآن مهتمة بمعرفة عدد التفاح الموجود في كل شركة تم تشكيلها حديثًا. في البداية ، يتسكع جميع الأصدقاء بشكل منفصل ، أي لا توجد شركة فيها أكثر من شخص. داشا ليس لديها تفاح وهي لا تشارك في الجمعيات.
الإدخال:
يحتوي السطر الأول على أعداد صحيحة n و k (2 & lt؛ = n & lt؛ = 300000، 0 & lt؛ = k & lt؛ = n - 1) - عدد أصدقاء داشا وعدد الأحداث. يحتوي السطر الثاني على n من الأرقام - ai (0 & lt ؛ = ai & lt ؛ = 10 ^ 9) - عدد التفاحات التي يمتلكها صديق داشا الأول. تحتوي الأسطر k التالية على رقمين u ، v (1 & lt ؛ = u ، v & lt ؛ = n). الحدث (u ، v) يعني أن الشركة مع صديق Dasha u-th قد انضمت إلى الشركة مع صديق v. & nbsp؛
الإخراج:
لكل استعلام من k اطبع عدد التفاحات في الشركة الجديدة.
<الجسم>
|
أدخل |
الإخراج |
|
3 2
|
3
6
|
|
2 1
999999999 0
1 2
|
999999999 |
(ج) إبراهيم أحمد ، 2018