D. Цайз

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Жералд $n - 1$ коридортой холбогдсон $n$ танхимтай цайзад байлаа. Ямар нэгэн танхимаас өөр нэгрүү очих зөвхөн нэг л зам байдаг. Иймээс граф нь мод. Эхлээд 0 дахь хугацаанд Жералд 1-р танхимд байсан. Мөн өөр нэг танхимд Жералд хайж буй эрднэс байгаа. Эрдэнэсийн байрлал мэдэгдэхгүй, бусад $n - 1$ танхимын алинд ч байх адил магадлалтай. Тэр зөвхөн эрдэнэстэй танхимд орох үед л эрдэнэс тэнд байгааг мэднэ. Яг тэр үед л Жералд эрдэнэсийг харах бөгөөд тэр агшин зорилгодоо хүрсэн мөчөөр тэмдэглэгдэнэ.

Коридор өөр өөр урттай. Коридорууд урт, танхимууд жижиг бөгөөд сайн гэрэлтүүлэгдсэн гэж үзнэ. Тэгэхээр Жералдын танхимд өнгөрүүлсэн хугацааг тооцохгүй. Цайз маш хуучин болохоор ямар нэгэн коридорт аль ч чиглэлд хоёр удаа л орвол шууд нуран унадаг.

Жералд эрдэнэсийг олох хүртлээ коридоруудыг ашиглан цайз дотор явна. Мэдээжээр Жералд эрдэнэсийг аль болохоор түргэн олохыг хүсэж байгаа. Өөрөөр хэлбэл тэр эрдэнэсийг олох дундаж хугацааг аль болохоор бага байлгахаар хөдөлнө гэсэн үг.

Коридор бүр хоёроос олон удаа хэрэглэгдэхгүй. Тиймээс Жералд бүх танхимд баталгаатай очиж болох стратегийг сонгоно.

Хэрэв эрдэнэс хоёр дахь танхимд байвал Жералд хоёр дахь танхим анх удаа орсон үедээ л түүнийг олно, тэр хугацааг $t_2$ гэе. Хэрэв эрдэнэс 3-р танхимд байрласан бол Жералд анх удаа 3-р танхимд орохдоо түүнийг олох болно. Тэр хугацааг $t_3$ гээд гэх мэтчилэн явбал эрдэнэсийг олох дундаж хугацаа $\frac{t_2 + t_3 + ... + t_n}{n - 1}$ байна.

Оролт

Хамгийн эхний мөр цайз дахь танхимуудыг тоог заах ганц $n (2 <= n <= 10^5)$ бүхэл тоог агуулна. Дараагийн $n - 1$ мөрүүд 3 бүхэл тоог агуулна. $i$ дахь мөр $a_i, b_i, t_i (1 <= a_i, b_i <= n, a_i != b_i, 1 <= t_i <= 1000)$ тоонуудыг агуулах ба тэдгээр нь харгалзан $i$ дахь коридортой холбогдсон танхимууд болон түүгээр явж өнгөрөх хугацаа. Эхлээд Жералд 1-р танхимд байгаа. Нэг танхимаас бусад бүх танхимд хүрч чадна.

Гаралт

Ганц бодит тоог хэвлэнэ: эрдэнэсийг олоход шаардагдах хайж буй хугацаа. Хариулт чинь зөв хариултаас $10^{-6}$-аас ихээр зөрөх учиргүй.

Орчуулсан: devman

Жишээ тэстүүд

Оролт
2
1 2 1
Гаралт
1.0
Оролт
4
1 3 2
4 2 1
3 2 3
Гаралт
4.333333333333334
Оролт
5
1 2 1
1 3 1
1 4 1
1 5 1
Гаралт
4.0

Тэмдэглэл

Эхний тестэд цайз зөвхөн хоёр танхимтай тул эрдэнэс 2-р танхимд байгаа нь тодорхой. Жералдад тэнд очихолд зөвхөн нэг минут шаардлагатай.

Хоёр дугаар тестэд Жералд эхний танхимаас зөвхөн 3-р танхимд очиж болно. 3-р танхимаас тэр нэг дүгээр танхим (1-р танхимд аль хэдийн очсон ба тэндээс өөр газарт хүрч чадахгүй) эсвэл 2 дугаархруу очиж болно. Тиймээс тэр 2-р танхимд очих ёстой. Тэндээс бусад бүх танхимд очсон тул 4-р танхимруу очно. Хэрэв эрдэнэс 3-р танхимд байрласан бол, Жералд түүнийг 1 минутад олно. Хэрэв 2-р танхимд байрласан бол 2 минутад олно. Хэрэв 4-р танхим байрласан бол Жералд түүнийг 3 минутад олно. Тиймээс дундаж хугацаа 2 минут болж байна.

Гурав дахь тестэд Жералд 4 танхимд зочлох ёстой: 2, 3, 4-р танхим. Бүгд зөвхөн 1-р танхимаас л хүрч болно. Тиймээс тэр бусад 4 танхимруу нэг нэгээр нь очин буцаж ирэх шаардлагатай. Хамгийн эхнийхэд нь тэр 1 минутад, хоёр дахид нь 3 минут, 3 дахид нь 5 минут, 4 дахид нь 7 минут. Дундаж нь 4 минут байна.

Сэтгэгдлүүдийг ачааллаж байна...