TR-O2. Ikki tarmoqni ulash
Ikki shaharchaning yo‘l tarmoqlari daraxt shaklida: birinchisida n₁ ta, ikkinchisida n₂ ta chorraha, yo‘llar uzunligi berilgan. Ularni bitta yangi yo‘l bilan ulamoqchi: uzunligi L, birinchi tarmoqning istalgan chorrahasidan ikkinchisining istalgan chorrahasiga.
Yangi tarmoqning diametri — eng uzoq ikki chorraha orasidagi masofa — imkon qadar kichik bo‘lsin. Eng kichik diametr qancha?
Kirish ma’lumotlari
Birinchi qatorda n₁, keyin n₁ − 1 qatorda u v w. So‘ng n₂ va n₂ − 1 qatorda u v w (ikkinchi tarmoq chorrahalari ham 1 dan raqamlangan). Oxirgi qatorda L.
Chiqish ma’lumotlari
Bitta son — eng kichik diametr.
Cheklovlar
1 ≤ n₁, n₂ ≤ 2·10⁵; 1 ≤ w, L ≤ 10⁶. Javob 64 bitli.
Misollar
3 1 2 1 2 3 1 5 1 2 1 2 3 1 3 4 1 4 5 1 1
4
1 1 7
7
4 1 2 10 2 3 1 3 4 1 2 1 2 100 5
115
Tushuntirish
1-misol: birinchi tarmoq — zanjir 1–2–3 (har yo‘l 1), ikkinchisi — zanjir 1–2–3–4–5 (har yo‘l 1). O‘rtalarni ulaymiz (2 va 3): diametr max(2, 4, 1 + 1 + 2) = 4.