Pommes
Problem
Dasha a n amis, chacun ai pommes. Tous les amis forment des sociétés qui ne se chevauchent pas. A tout moment, deux sociétés peuvent fusionner. Dasha se souvenait soigneusement de toutes les actions de ses amis. Maintenant, elle est intéressée de savoir combien de pommes il y avait dans chaque entreprise nouvellement créée. Au départ, tous les amis traînent séparément, c'est-à-dire il n'y a pas d'entreprise où il y a plus d'une personne. Dasha n'a pas de pommes et elle ne fait pas partie d'associations.
Saisie :
La première ligne contient des nombres entiers n et k ( 2 <= n <= 300000, 0 <= k <= n - 1 ) - le nombre d'amis de Dasha et le nombre d'événements. La deuxième ligne contient n nombres - ai (0 <= ai <= 10^9) - le nombre de pommes que possède le i-ième ami de Dasha. Les k lignes suivantes contiennent deux nombres u, v ( 1 <= u, v <= n). L'événement (u, v) signifie que l'entreprise avec le u-ième ami de Dasha a rejoint l'entreprise avec le v-ième ami.
Sortie :
Pour chacune des k requêtes, imprimez le nombre de pommes dans la nouvelle société.
Entrez
Sortie
3 2
2 1
999999999 0
1 2
999999999
(c) Ibrahim Ahmad, 2018