D. Баярт модны үдэшлэг

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

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

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

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

Өнөөдөр Богданы төрсөн өдөр ба ээж нь түүнд $n$ оройгоос бүрдэх мод өгсөн. Модны $i$ ирмэг бүр дээр $x_{i}$ тоо бичигдсэн байсан. Та мартсан тохиолдолд мод нь чиглэлгүй холбогдсон циклгүй граф байна. Бэлэг бэлэглэгдсэний дараа Богданы үдэшлэгт $m$ зочин цуварч ирсэн. $i$-р зочин ирэх үед Богдан боломжит хоёр үйлдлийн яг нэгийг нь гүйцэтгэнэ:

  1. $y_{i}$ тоо ба $a_{i}$ болон $b_{i}$ хоёр орой сонгоно. Үүний дараа тэр хамгийн богино замыг ашиглан (мэдээж ийм зам нь модонд давтагдахгүй) $a_{i}$ оройгоос $b_{i}$ оройруу модны ирмэгүүдийн дагуу хөдлөнө. Тэр $j$ ирмэгээр хөдлөх бүртээ байгаа $y_{i}$ тоогоо -р солих буюу $y_{i}$ тоог $x_{j}$ тоонд хуваагаад гарсан хариуны бүхэл хэсгээр солино.
  2. $p_{i}$ ирмэг сонгох ба дээр нь бичээтэй байгаа $x_{p_{i}}$ тоог $c_{i} < x_{p_{i}}$ бүхэл тоон утгаар солино.

Богдан зочидоо асрахын зэрэгцээ үйл явцыг хялбарчлахаар шийдсэн. Зочидын хүссэн бүх үйлдлийг гүйцэтгэж эхний төрлийн $i$ бүрийн хувьд гарах $y_{i}$ утгыг гаргах програм бич.

Оролт

Оролтын эхний мөрөнд бүхэл тоон утгууд $n$ ба $m$ ($2 ≤ n ≤ 200 000$, $1 ≤ m ≤ 200 000$) байх ба харгалзан Богданд ээжийнх нь бэлэглэсэн модонд байх оройнуудын тоо ба үдэшлэгт ирсэн зочдын тоо байна.

Дараагийн $n - 1$ мөрөнд ирмэгүүдийн тайлбар байна. Эдгээр мөрүүдийн $i$-р мөрөнд гурван бүхэл тоон утга $u_{i}$, $v_{i}$ ба $x_{i}$ ($1 ≤ u_{i}, v_{i} ≤ n$, $u_{i} ≠ v_{i}$, $1 ≤ x_{i} ≤ 10^{18}$) байх ба $u_{i}$ болон $v_{i}$ оройнуудыг холбосон ирмэгийг дээр нь анх бичээтэй байсан $x_{i}$ тоотой хамт илтгэнэ.

Дараагийн $m$ мөрөнд Богданы зочдын хүссэн үйлдлүүдийг тодорхойлно. Тодорхойлолт бүр гурав эсвэл дөрвөн бүхэл тоон утга агуулах ба доорх хоёр боломжит хэлбэрийн аль нэг нь байна:

  • $1$ $a_{i}$ $b_{i}$ $y_{i}$ нь эхний төрлийн үйлдлийг сонгосон зочинтой харгалзана.
  • $2$ $p_{i}$ $c_{i}$ нь хоёр дахь төрлийн үйлдлийг сонгосон зочидтой харгалзана.

Бүх даалгаварууд зөв байх ба өөрөөр хэлбэл $1 ≤ a_{i}, b_{i} ≤ n$, $1 ≤ p_{i} ≤ n - 1$, $1 ≤ y_{i} ≤ 10^{18}$ ба $1 ≤ c_{i} < x_{p_{i}}$ байх ба энд $x_{p_{i}}$ нь хугацааны тухайн мөчид $p_{i}$ дээр бичигдсэн тоог илэрхийлэх ба буурсан байж болох анхны $x_{p_{i}}$-тэй тэнцүү байх шаардлагагүй. Ирмэгүүд оролтонд өгөгдсөн дарааллаараа $1$-c $n - 1$ хүртэл дугаарлагдана.

Гаралт

Эхний төрлийн үйлдлийг сонгосон зочин бүрийн хувьд $a_{i}$-с $b_{i}$ хүртэлх зам дээрх $y_{i}$ утгын өөрчлөлтийн үр дүнг хэвлэ.

Орчуулсан: Г.Мэндбаяр

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

Оролт
6 6
1 2 1
1 3 7
1 4 4
2 5 5
2 6 2
1 4 6 17
2 3 2
1 4 6 17
1 5 5 20
2 4 1
1 5 1 3
Гаралт
2
4
20
3
Оролт
5 4
1 2 7
1 3 3
3 4 2
3 5 5
1 4 2 100
1 5 4 1
2 2 2
1 1 3 4
Гаралт
2
0
2

Тэмдэглэл

Эхэндээ мод дараах байдалтай харагдана:

Эхний даалгаварын хариуд: = 2

Гуравдугаар ирмэг өөрчлөгдсөний дараа мод дараах байдалтай харагдана:

Хоёрдугаар даалгаварын хариуд: = 4

Гурав дахь даалгавар дээр анхны болон эцсийн орой таарна буюу хариулт нь анхны тоо болох 20 байх болно.

Дөрөвдүгээр ирмэг өөрчлөгдсөний дараа мод дараах байдалтай харагдана:

Сүүлийн даалгавар дээр хариулт: = 3

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