TR-M3. Eng uzoq safar

Viloyatdagi n ta qishloq n − 1 ta yo‘l bilan daraxt shaklida ulangan, j-yo‘l uzunligi wⱼ. Har bir qishloq maktabi o‘zidan eng uzoq qishloqqa ekskursiya rejalashtirmoqda.

Har bir qishloq uchun undan eng uzoq qishloqqacha masofani toping.

Kirish ma’lumotlari

Birinchi qatorda n. Keyingi n − 1 qatorda u v w.

Chiqish ma’lumotlari

Bitta qatorda n ta son: i-son — i-qishloqdan eng uzoq masofa.

Cheklovlar

1 ≤ n ≤ 2·10⁵; 1 ≤ w ≤ 10⁹. Javoblar 32 bitga sig‘masligi mumkin.

1-misol: 1-qishloqdan eng uzoq — 4 (2 + 7 = 9); 4-qishloqdan — 3 (7 + 2 + 5 = 14).