Module: ayrık küme sistemi


Problem

3 /9


Elmalar

Problem

Dasha'nın n arkadaşı var, her birinin biri elması var. Tüm arkadaşlar örtüşmeyen şirketler oluşturur. Her an iki şirket birleşebilir. Dasha, arkadaşlarının tüm eylemlerini dikkatlice hatırladı. Şimdi her yeni kurulan şirkette kaç tane elma olduğunu bilmekle ilgileniyor. Başlangıçta, tüm arkadaşlar ayrı ayrı takılır, yani. birden fazla kişinin olduğu şirket yoktur. Dasha'nın elması yok ve derneklerde yer almıyor.

Giriş:
İlk satır n ve k tamsayılarını içerir ( 2 <= n <= 300000, 0 <= k <= n - 1 ) - Dasha'nın arkadaşlarının sayısı ve olayların sayısı. İkinci satır n sayı içerir - ai (0 <= ai <= 10^9) - Dasha'nın i. arkadaşının sahip olduğu elma sayısı. Sonraki k satır iki sayı u, v içerir ( 1 <= u, v <= n). (u, v) olayı, Dasha'nın u-th arkadaşı olan şirketin v-th arkadaşı olan şirkete katıldığı anlamına gelir. 

Çıktı:
Her k sorgu için yeni şirketteki elma sayısını yazdırın.


(c) İbrahim Ahmed, 2018

time 2000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!

Gir Çıktı
3 2
1 2 3
1 2
1 3
3
6
2 1
999999999 0
1 2
 999999999