E. Загвартай хөлдөөх

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

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

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

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

Энэ өвөл үнэхээр... тийм ээ танд нэгэн санаа төрчээ :-) Нводск-ийн замын сүлжээ нь ямар ч 2 уулзварын хооронд зам оршин байхаар $n - 1$ ширхэг 2 урсгалтай замуудаар холбогдсон $n$ ширхэг замын уулзвараас тогтдог байжээ. Нэгэн үйл ажиллагааны зохион байгуулагчид нь оролцогчдыг байрлуулах нэгэн газрыг($v$ уулзвар) сонгох хэрэгтэй болсон ба мөн тэмцээнүүдийг зохиох бас нэгэн газрыг($u$ уулзвар) олох хэрэгтэй болжээ. Нэг талаас, зохион байгуулагчид нь тэмцээнд оролцогчдыг хотын талаар ярилцан алхаж өөрсдийн хотыг үзээсэй хэмээн хүсэж байв (ийм учраас $v$ болон $u$-ын хоорондох зай $l$-ээс багагүй байх ёстой юм). Нөгөө талаас тэд оролцогчдыг хөлдөх, осгохыг хүсэхгүй байгаа юм (ийм учраас $v$ болон $u$-ын хоорондох зай $r$-ээс ихгүй байх ёстой байв). Түүнчлэн гудамж бүрийн хувьд бид уг гудамжны гоо үзэсгэлэн болох $0$-ээс $10^{9}$ хүртэлх нэгэн бүхэл тоог мэдэж байв. Таны даалгавар бол эдгээр уулзваруудын хооронд тэмцээнд оролцогчдыг аялуулах уг хязгаарлалтуудыг хангаж байх хамгийн их дундаж гоо үзэсгэлэн бүхий замын маршрутыг сонгох ажээ. Бид дундаж гоо үзэсгэлэн гэдгээр уг замын маршрутын дагуух бүх замуудын гоо үзэсгэлэнгүүдийн дарааллын медианыг тэмдэглэнэ.

Уг бодлогыг илүү дэлгэрэнгүй тайлбарлавал: $k$ урттай нэгэн замын маршрут өгөгдсөн байг. $a_{i}$ нь яг $k$ ширхэг элемент агуулах үл буурах дараалал байг. Түүнчлэн уг дарааллын элемент болгон нь яг уг элементтэй тэнцүү гоо үзэсгэлэн бүхий зам уг маршрутын турш хэдэн удаа гарч ирсэнтэй ижил тоогоор уг дараалалд орсон байх юм. Өөрөөр хэлбэл бид уг дарааллыг маршрутын дагуух замуудын гоо үзэсгэлэнгүүдийг үл буурах эрэмбээр байрлуулсан дараалал гэж ойлгож болно. Тэгвэл уг замын маршрутын медиан нь $a_{⌊k / 2⌋}$ дугаартай тоо болох бөгөөд энд бид уг дарааллын элементүүдийг 0-ээс эхлэн дугаарлагдсан байна гэж үзнэ. $⌊x⌋$ гэдэг нь $х$ тооноос үл хэтрэх хамгийн ойрхон бүхэл тоог илэрхийлнэ.

Жишээлбэл $a = {0, 5, 12}$ байвал медиан нь $5$ болох ба хэрэв $a = {0, 5, 7, 12}$ байвал медиан нь $7$ болох юм.

Мөн түүнчлэн дор хаяж нэг ширхэг тохиромжтой замуудын маршрут оршин байх юм.

Оролт

Эхний мөрөнд 3-н бүхэл тоо $n$, $l$, $r$ ($1 ≤ l ≤ r < n ≤ 10^{5}$) өгөгдөнө.

Дараагийн $n - 1$ мөрөнд Нводск-ийн замуудын тайлбар өгөгдөх ба мөр болгонд 3-н бүхэл тоо $a_{i}$, $b_{i}$, $c_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n$, $0 ≤ c_{i} ≤ 10^{9}$, $a_{i} ≠ b_{i}$)-ууд өгөгдөх ба эдгээр нь $a_{i}$ болон $b_{i}$ уулзварууд нь хоорондоо $c_{i}$ гоо үзэсгэлэнтэй нэгэн гудамжаар холбогдсон болохыг илэрхийлэх юм.

Гаралт

Харгалзан тэмцээнд оролцогчдыг байрлуулах болон тэмцээнүүдийг зохион байгуулах уулзваруудын дугаарууд болох 2 бүхэл тоог хэвлэнэ үү. Хэрэв хэд хэдэн боломжит хувилбар байвал тэдгээрийн алийг нь ч хэвлэсэн болно.

Орчуулсан: Баатархүү

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

Оролт
6 3 4
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
Гаралт
4 1
Оролт
6 3 4
1 2 1
2 3 1
3 4 1
4 5 2
5 6 2
Гаралт
6 3
Оролт
5 1 4
1 2 1
1 3 4
3 4 7
3 5 2
Гаралт
4 3
Оролт
8 3 6
1 2 9
2 3 7
3 4 7
4 5 8
5 8 2
3 6 3
2 7 4
Гаралт
5 1

Тэмдэглэл

Эхний жишээнд бүх замууд нь ижилхэн гоо үзэсгэлэнтэй байна. Энэ нь эерэг урт бүхий бүх маршрут-ууд нь ижилхэн медиантай байна гэсэн үг юм. Түүнчлэн $3$-аас $4$ хүртэлх урттай ямар ч замуудын маршрут нь бидний хариу болж байна.

2-дахь жишээнд хот нь 1 - 2 - 3 - 4 - 5 - 6 байдалтай харагдана. Сүүлийн 2 замууд нь илүү гоо үзэсгэлэнтэй учраас бид эдгээр 2 замыг 2-ууланг нь агуулах тохиромжтой урт бүхий замын маршрутыг сонгох хэрэгтэй юм. Ийм байх замууд нь $2$ болон $6$-р уулзваруудын хооронд мөн $3$ болон $6$-р уулзваруудын хооронд оршин байх ажээ.

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