manzanas
Problem
Dasha tiene n amigos, cada uno tiene i manzanas. Todos los amigos forman empresas que no se superponen. En cualquier momento, dos empresas pueden fusionarse. Dasha recordó cuidadosamente todas las acciones de sus amigos. Ahora le interesa saber cuántas manzanas había en cada empresa recién formada. Inicialmente, todos los amigos pasan el rato por separado, es decir. no hay empresa donde haya más de una persona. Dasha no tiene manzanas y no participa en asociaciones.
Entrada:
La primera línea contiene números enteros n y k ( 2 <= n <= 300000, 0 <= k <= n - 1 ) - el número de amigos de Dasha y el número de eventos. La segunda línea contiene n números - ai (0 <= ai <= 10^9) - el número de manzanas que tiene el i-ésimo amigo de Dasha. Las siguientes k líneas contienen dos números u, v ( 1 <= u, v <= n). El evento (u, v) significa que la empresa con el u-ésimo amigo de Dasha se ha unido a la empresa con el v-ésimo amigo.
Salida:
Para cada una de las k consultas, imprima el número de manzanas en la nueva empresa.
|
Entrar |
Salida |
|
3 2
|
3
6
|
|
2 1
999999999 0
1 2
|
999999999 |
(c) Ibrahim Ahmad, 2018