Maçãs
Problem
Dasha tem n amigos, cada um tem uma i maçã. Todos os amigos formam empresas que não se sobrepõem. A qualquer momento, duas empresas podem se fundir. Dasha lembrou-se cuidadosamente de todas as ações de suas amigas. Agora ela está interessada em saber quantas maçãs havia em cada empresa recém-formada. Inicialmente, todos os amigos saem separadamente, ou seja, não há empresa onde haja mais de uma pessoa. Dasha não tem maçãs e não participa de associações.
Entrada:
A primeira linha contém inteiros n e k ( 2 <= n <= 300000, 0 <= k <= n - 1 ) - o número de amigos de Dasha e o número de eventos. A segunda linha contém n números - ai (0 <= ai <= 10^9) - o número de maçãs que o i-ésimo amigo de Dasha tem. As próximas k linhas contêm dois números u, v ( 1 <= u, v <= n). O evento (u, v) significa que a empresa com o u-ésimo amigo de Dasha ingressou na empresa com o v-ésimo amigo.
Saída:
Para cada uma das k consultas, imprima o número de maçãs na nova empresa.
|
Entrar |
Saída |
|
3 2
|
3
6
|
|
2 1
999999999 0
1 2
|
999999999 |
(c) Ibrahim Ahmad, 2018