G. Аалзнуудын чөтгөрийн төлөвлөгөө

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

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

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

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

Аалзнууд бол Ом Номын хуучны дайснууд. Тэд түүний иддэг чихрэнд маш дуртай бөгөөд энэ нь өөрсдийн дуртай чихэрнээс мангасыг холдуулдаг шалтгаан юм. Тэд Ом Номыг урхинд хийх чөтгөрийн санааг гаргаж иржээ..

$n$ ширхэг зангилаануудтай, эдгээр зангилаануудыг холбосон $n - 1$ уяанаас бүрдсэн бүтэц байна гэж бодъё. Ийм бүтэцтэй уяанууд холбогдон мод шиг хэлбэртэй байна. Уяа бүр өөрийн уртаараа холбогдсон байна. Чихэр зангилаа $x$ дээр байрлаж байна. Ом Ном энэ чихрийг идэхийг маш их хүсдэг.

$y$ аалзнууд түүнийг зогсоохыг оролдоно. Тэд чихрийг орооцолдуулахаар шийдэх ба бүтцийн зарим хэсгийг аалзны шүлсээр торлохоор болжээ. Тиймээс чихрийг бүтцийн хамгийн том хэсэгт уях юм.

Аалз бүр дурын $a$ болон $b$ 2 уяануудын хоорондох зайг бүхэлд нь бүрхэж байхаар торлож чадна. Тиймээс $y$ ширхэг аалзнууд $y$ ширхэг замыг торлож чадна. Эдгээр $y$ ширхэг замууд бие биетэйгээ огтлолцох боломжтой. Аалзнууд дараах нөхцлүүдийг хангахыг хүсч байгаа: * Чихрийг агуулж байгаа зангилаа дор хаяж нэг торлогдсон уяатай холбогдсон байх ёстой * Торлогдсон уяанууд хоорондоо холбогдсон байх ёстой (чихэртэй холбогдоогүй уяанууд хоорондоо холбогдсон байх ёстой ямар санаа байж болох вэ?) * Торлогдсон уяаны нийт урт хамгийн их байх.

Эдгээр аалзнууд чихрээ торлох бүтцээ шийдээгүй байгаа бөгөөд хэр их аалзнууд сүлжээг бүрхэх талаар асууна. Тэдэнд туслахын тулд $x$ болон $y$-н боломжит хариунуудыг тооцоолно уу.

Оролт

Эхний мөрөнд бүтцийн зангилааны тоо болон аалзнуудын асуухыг хүсч буй асуултуудын тоо болох $n$, $q$ ($1 ≤ n, q ≤ 10^{5}$) тоонууд өгөгдөнө.

Дараагийн $n-1$ ширхэг мөрөнд уяануудын бүтэц өгөгдөнө. $i$ дэхь мөрөнд 3-н бүхэл тоонууд $u_{i}, v_{i}, l_{i}$ ($1 ≤ u_{i}, v_{i} ≤ n$, $u_{i} ≠ v_{i}$, $1 ≤ l_{i} ≤ 1000$) өгөгдөнө. Эдгээр нь $l_{i}$ урттай $i$ дэхь уяа нь $u_{i}$, $v_{i}$ 2 зангилааны хооронд байрлахыг илэрхийлнэ.

Дараагийн $q$ ширхэг мөрөнд аалзнуудын асуултуудын тайлбар өгөгдөнө. Тэд өөрсдийн асуултыг чамаас асуухдаа онцгой хэлбэрээр асуужээ.

Дараагийн $q$ ширхэг мөрний мөр болгон 2 тоонууд $x_{i}, y_{i}$ агуулна. Аалзнуудын эхний асуулт нь $x = x_{1}, y = y_{1}$.

Аалзнуудын $i$ дэхь асуултын $x$, $y$ утгуудыг тооцоолхын тулд та дараах томьёог ашиглах шаардлагатай:

Энд $Ans_{i - 1}$ нь $(i - 1)$ дэхь асуултын хариу болох торлогдсон уяануудын нийт урт болно.

Дараах тэнцэтгэл биш хангагдана: $1 ≤ x_{i}, y_{i} ≤ n$

Гаралт

Аалзнуудын асуулт болгоны хариу $Ans_{i}$-г ялгаатай мөрөнд нэг бүхэл тоогоор хэвлэнэ үү. Энд $Ans_{i}$ нь тохирсон нөхцлийг хангасан торлогдсон уяануудын нийт урт болно.

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

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

Оролт
6 3
1 2 2
2 3 2
3 4 2
4 6 1
3 5 10
3 1
2 5
1 1
Гаралт
14
13
17
Сэтгэгдлүүдийг ачааллаж байна...