TR-E4. Juft qadamli juftliklar

Bog‘da n ta skameyka n − 1 ta yo‘lka bilan daraxt shaklida ulangan. Ikki skameyka orasidagi masofa — ular orasidagi yagona yo‘ldagi yo‘lkalar soni.

Navbatchilar ikkitadan bo‘lib skameykalarga o‘tirishadi va orasidagi masofa juft bo‘lsagina bir-birini ko‘ra olishadi. Nechta (tartibsiz) skameyka juftligi orasidagi masofa juft?

Kirish ma’lumotlari

Birinchi qatorda n. Keyingi n − 1 qatorda yo‘lkalar u v.

Chiqish ma’lumotlari

Bitta son — masofasi juft bo‘lgan juftliklar soni.

Cheklovlar

1 ≤ n ≤ 2·10⁵. Javob 32 bitga sig‘masligi mumkin.

1-misol (yulduz): markazdan hamma 1 qadam, chetdagi har ikkitasi orasida 2 qadam — C(3, 2) = 3.