D. Дразил ба өглөөний дасгал

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

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

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

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

Дразил болон Варда бол хос өтнүүд юм. Тэд хүүхдээ төрүүлэхийн тулд тохирох газрыг олохыг хүсэж байгаа. Тэд нүх агуулсан тохиромжтой газар олжээ. Нүх олон өрөөтэй. Зарим өрөөнүүд жижигхэн хонгилоор холбогдсон учир өтнүүд үүгээр дамжих боломжтой.

Өрөөнүүд болон жижигхэн хонгилуудыг графикт өнцөг болон ирмэг гэж үзье. Энэхүү график нь мод хэлбэртэй. Өөрөөр хэлбэл аль ч өнцөгүүдийн хооронд онцгой нэг зам байдаг.

Зарим өрөө нь навч бөгөөд босоо хонгилоор газрын гадаргатай холбогдсон. Энд навч нь газрын гадарга уруу гарч буй зөвхөн нэг л хонгилтой байна.

Өрөө болгонд нэг өт амьдарч болохуйц том хэмжээтэй. Өт хонгилд амьдарч чадахгүй.

Дразил болон Варда өөрсдийн хүүхдүүдээ сургахаар төлөвлөж байгаа бөгөөд тэд өөрсдийн хүүхдүүдийг өглөө болгон боссоныхоо дараа өглөөний дасгал хийхийг хүсч байгаа.

Өглөө болоход бүх хүүхдүүд нэгэн зэрэг босож бусадтайгаа цугларахын тулд хамгийн холын замыг сонгоно (эдгээр хүүхдүүд нь залхуу учраас бүгд дасгалыг байж болох хамгийн орой хийхийг хүсдэг).

Дразил болон Варда нь эхний хүүхэд гадагш гарж ирэх хугацаанаас эхлэн сүүлийн хүүхэд гадагш гарж ирэх хүртэл хугацааг $l$-ээс их байлгахыг хүсэхгүй байгаа (үгүй бол хүүхдүүд газрын гадарга дээр таран тэднийг хамтад нь дасгал хийлгэхэд хэцүү болно).

Үүнээс гадна тэдний хүүхдүүдийн байрлах өрөөнүүд нь хоорондоо холбогдсон байх ёстой. Өөрөөр хэлбэл аль ч 2 хүүхэдтэй өрөөний хооронд дамжихын тулд хүүхэдтэй өрөөнүүдээр л дамжих ёстой.

Дээрх нөхцлүүдийг хангаж байхаар хамгийн ихдээ хэдэн хүүхэдтэй болох боломжтой вэ? Дразил болон Варда нь хариултыг ялгаатай $l$-үүдийн утганд мэдэхийг хүсэж байгаа.

(Дразил болон Варда нь хүүхдүүдтэйгээ хамт нүхэнд амьдардаггүй.)

Оролт

Эхний мөрөнд нүхэнд байгаа өрөөний тоо болох нэг бүхэл тоо $n$ ($2 ≤ n ≤ 10^{5}$) өгөгдөнө.

Үүний дараа $n-1$ ширхэг мөрөнд мөр болгон 3-н бүхэл тоонууд $x$, $y$, $v$ ($1 ≤ x, y ≤ n$, $1 ≤ v ≤ 10^{6}$) агуулна. Эдгээр нь $x$ болон $y$ 2 өрөөний хооронд явахын тулд $v$ хугацаа зарцуулахыг илэрхийлнэ.

Энд аль ч өрөөнөөс газрын гадарга уруу гарах хугацааг адилхан гэж үзнэ.

Дараагийн мөрөнд $l$-ийн ялгаатай утгуудын тоо болох нэг бүхэл тоо $q$ ($1 ≤ q ≤ 50$) өгөгдөнө.

Сүүлийн мөр $q$ ширхэг тоо агуулна. Тоо болгон нь $l$ ($1 ≤ l ≤ 10^{11}$)-ийн утгыг илэрхийлнэ.

Гаралт

Та $q$ ширхэг мөр хэвлэнэ үү. Мөр болгон $l$-ын утганд тохирох хариултыг илэрхийлэхээр нэг бүхэл тоог агуулна.

Орчуулсан: Энхлут

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

Оролт
5
1 2 3
2 3 4
4 5 3
3 4 2
5
1 2 3 4 5
Гаралт
1
3
3
3
5
Оролт
12
5 9 3
2 1 7
11 7 2
6 5 5
2 5 3
6 7 2
1 4 4
8 5 7
1 3 8
11 12 3
10 8 2
10
13 14 14 13 13 4 6 7 2 1
Гаралт
10
10
10
10
10
3
3
5
2
1

Тэмдэглэл

Эхний жишээнд нүх дараах байдалтай байна. Өрөө 1 ба 5 нь навч, тиймээс эдгээр нь газрын гадаргатай босоо хонгилоор холбогдсон. Өрөө $1-5$-уудаас газрын гадарга хүрэн хамгийх хол зай нь $12, 9, 7, 9, 12$.

Хэрвээ l = 1 бол бид зөвхөн ганцхан өрөө сонгоно.

Хэрвээ l = 2..4 бол бид өрөө 2, 3, 4-ыг хариугаараа сонгон авч болно.

Хэрвээ l = 5 бол бид бүх өрөөг сонгож болно.

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