Masala #0173
Daraxtlarni ulash
Daraxt deb bog’langan, ta tugun va ta shoxdan iborat grafga aytiladi.
Sizga mos ravishda ta va ta tugundan iborat bo’lgan ikkita daraxt berilgan. Birinchi daraxtning biror tugunini ikkinchi daraxtning biror tuguniga ulash orqali bitta yangi daraxt hosil qilindi. Sizning vazifangiz esa hosil bo’lgan daraxtda ixtiyoriy ikkita tugun orasidagi maksimal masofa eng kamida qancha bo’lishi mumkinligini topishdan iborat.
Ikki tugun orasidagi masofa deb, bu tugunlar orasidagi shoxlar soniga aytiladi.
Birinchi qatorda bitta butun soni - birinchi daraxt tugunlari soni . Ikkinchi qatorda esa ta va ko’rinishidagi juftliklar, ya’ni birinchi daraxt bog’lanishlari beriladi . Keyingi qatorda esa xuddi shu tartibda ikkinchi daraxt beriladi, dastlab butun soni, so’ngra ta va juftliklar .
Bitta butun son – masalaning javobi.
# | input.txt | output.txt |
---|---|---|
1 |
3 1 2 1 3 4 1 2 2 3 2 4 |
3 |
Quyidagi rasmda birinchi daraxt sariq rangda, ikkinchi daraxt ko’k rangda berilgan, ularni bog’lovchi shox esa qizilda berilgan, yangi daraxtdagi eng uzun masofa 3.