Die Äpfel
Problem
Dasha hat n Freunde, jeder hat ai Äpfel. Alle Freunde bilden nicht überlappende Gesellschaften. Zu jeder Zeit können sich die beiden Unternehmen zusammenschließen. Dasha erinnerte sich sorgfältig an alle Handlungen ihrer Freunde. Jetzt ist sie daran interessiert zu wissen, wie viele Äpfel es in jedem neu gegründeten Unternehmen gab. Anfangs hängen alle Freunde getrennt ab, dh es gibt keine Firma, in der es mehr als eine Person gibt. Dasha hat keine Äpfel und nimmt nicht an Vereinigungen teil.
Eingabe:
Die erste Zeile enthält die ganzen Zahlen n und k ( 2 <= n <= 300.000, 0 <= k <= n - 1 ) - die Anzahl der Dasha-Freunde und die Anzahl der Ereignisse. In der zweiten Zeile n Zahlen - ai (0 <= ai <= 10^9) - die Anzahl der Äpfel, die ich habe, ist Dasha's Freund. In den folgenden k-Zeilen gibt es zwei Zahlen u, v ( 1 <= u, v <= n). Das Ereignis (u, v) bedeutet, dass ein Unternehmen mit einem u-ten Freund von Dasha einem Unternehmen mit einem v-ten Freund beigetreten ist.
Ausgabe:
Geben Sie für jede der k-Anfragen die Anzahl der Äpfel in der neuen Firma an.
|
Eingabe |
Ausgabe |
|
3 2
1 2 3
1 2
1 3
|
3
6
|
|
2 1
999999999 0
1 2
|
999999999 |
(c) Ibrahim Ahmad, 2018