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.
|
Gir |
Çıktı |
|
3 2
|
3
6
|
|
2 1
999999999 0
1 2
|
999999999 |
(c) İbrahim Ahmed, 2018