Masala #0796

Xotira 16 MB Vaqt 1000 ms Qiyinchiligi 35 %
14

  

Maxsus tugunlar

Sizga N ta tugundan iborat daraxt berilgan. Daraxt tugunlari 1 dan N gacha raqamlangan hamda daraxtning ildizi 1 - tugun hisoblanadi. Daraxtni shakllantirish uchun \(N-1\) ta yo’naltirilmagan qirra beriladi. Daraxtning i - tugunida \(A_i\) soni yozilgan.

Daraxt ildizidan K - tugunga borish yo’lida uchraydigan barcha qiymatlar har xil bo’lsa K - tugun maxsus tugun deyiladi.

Sizning vazifangiz berilgan daraxtda nechta maxsus tugun borligini aniqlashdan iborat.


Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun son, \(N(1 ≤ N ≤ 10^5)\) soni kiritiladi. Ikkinchi qatorda \(N\) ta butun son, har bir tugun uchun \(A(0 ≤ A_i ≤ 10^6)\) to’plam elementi qiymati kiritiladi. Uchinchi qatordan boshlab \(N-1\) ta qatorda ikkitadan butun son, \(u, v(1 ≤ u, v ≤ N, u \ne v)\) daraxt qirralari bog’lab turgan tugunlar ro’yxati kiritiladi.


Chiquvchi ma'lumotlar:

Berilgan daraxtdagi maxsus tugunlar sonini chop eting!


Misollar
# input.txt output.txt
1
7
1 7 2 3 7 2 5
1 2
1 3
2 4
2 5
3 6
3 7
5
Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin