014-D.md

Хоёр зам

Бидний мэдэхээр Бобын ах нь Флатландад амьдардаг. Флатланд улс нь $n$ хоттой бөгөөд тэдгээрийг холбосон $n-1$ замтай. Хотууд нь $1$-с $n$ хүртэл дугаарлагдсан бөгөөд та аль ч хотоос аль ч хотруу очих боломжтой байна.

Бобын ахын ажилладаг "Хоёр зам" компани Флатландад 2 чиглэл засах тендерт шалгарчээ. Чиглэл гэдэг нь нэг хотоос нөгөө хотруу очиход ашиглах замуудын дараалал юм. Компани чиглэлүүдээ хүссэнээрээ сонгож болох бөгөөд зөвхөн сонгосон 2 чиглэл огтлолцохгүй байх ганц шаардлага тавигдсан (Огтлолцохгүй байна гэдэг нь нэг хотоор 2 чиглэл хоёул дайрахгүй байна).

"Хоёр зам" компанийн авах мөнгө нь нийт зассан замын урт байх бөгөөд бүх зам $1$ урттай болно. Нэг чиглэлийн урт нь үүнд ашиглагдаж буй замуудын нийт урттай тэнцүү болно. Иймд компанийн авч болох хамгийн их мөнгөний хэмжээг олно уу.

Оролт

Эхний мөрөнд нийт хотуудын тоо болох $n$ ($2 ≤ n ≤ 200$) өгөгдөнө. Дараагийн $n-1$ мөрөнд хоорондоо холбогдсон хотуудыг илэрхийлэх $a_i$, $b_i$ ($1 ≤ a_i, b_i ≤ n$) хос тоонууд байна.

Гаралт

Авч болох хамгийн их мөнгөний хэмжээ болох ганц тоог хэвлэ.

-- zoloogg