Mele
Problem
Dasha ha n amici, ognuno ha unai mela. Tutti gli amici formano società non sovrapposte. In qualsiasi momento, due società possono fondersi. Dasha ricordava attentamente tutte le azioni dei suoi amici. Ora è interessata a sapere quante mele c'erano in ogni nuova azienda. Inizialmente, tutti gli amici escono separatamente, ad es. non c'è azienda dove c'è più di una persona. Dasha non ha mele e non partecipa ad associazioni.
Inserimento:
La prima riga contiene i numeri interi n e k ( 2 <= n <= 300000, 0 <= k <= n - 1 ) - il numero di amici di Dasha e il numero di eventi. La seconda riga contiene n numeri - ai (0 <= ai <= 10^9) - il numero di mele che ha l'i-esimo amico di Dasha. Le successive k righe contengono due numeri u, v ( 1 <= u, v <= n). L'evento (u, v) significa che la compagnia con l'u-esimo amico di Dasha si è unita alla compagnia con il v-esimo amico.
Risultato:
Per ciascuna delle k query stampa il numero di mele nella nuova azienda.
|
Entra |
Uscita |
|
3 2
|
3
6
|
|
2 1
999999999 0
1 2
|
999999999 |
(c) Ibrahim Ahmad, 2018