E. Тавас ба замын сүлжээ

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

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

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

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

Тавас Тавасполист амьдардаг. Тавасполист $n - 1$ ширхэг хоёр чиглэлт замаар холбогдсон $1$-ээс $n$ хүртэл дугаарлагдсан $n$ хот байдаг. Дурын хоёр хотын хооронд замуудын тусламжтайгаар явж болдог. Мөн зам бүр тодорхой урттай байв.

Тавасын дуртай тэмдэгт мөр нь хоёртын тэмдэгт мөр буюу зөвхөн $0$ болон $1$-үүдээс тогтох тэмдэгт мөр юм. Дурын $s = s_{1}s_{2}... s_{k}$ хоёртын тэмдэгт мөрийн хувьд, $T(s)$-ээр түүний "сайн чанар" гэх ойлголтыг тэмдэглэе.

Энэ тэмдэгт мөрөнд $x_{1}, x_{2}, ..., x_{m}$ гэсэн уртуудтай $m$ ширхэг $1$-үүдийн хэрчим байгаа гэвэл $T(s) = \sum\limits_{i=1}^{m} f_{x_i}$ гэж тодорхойлъё.

Энд $f$ нь өгөгдсөн дараалал (Хэрэв $m = 0$ бол $T(s) = 0$). Мөн $s$ тэмдэгт мөрийн $1$-үүдийн хэрчим гэдэг нь дараалсан $1$-үүдээс тогтох хамгийн урт дэд тэмдэгт мөрийг хэлнэ.

Тавас чамаас $q$ хүсэлтийг нь гүйцэтгэж өгөхийг хүсчээ. Хүсэлт бүрт тэр чамд $v, u, l$ гэсэн тоонууд өгөх ба чи дараахь тоог хэвлэх ёстой:

$v$ хотоос $u$ хотруу очих замуудын дарааллыг авч үзье: $e_{1}, e_{2}, ..., e_{x}$.

Эхлээд дурын $i$ бүрийн хувьд $b_{i} = 1$ байх гарцаагүй бөгөөд хүрэлцээтэй нөхцөл нь $l ≤ w(e_{i})$ байхаар $x$ урттай $b$ бинар тэмдэгт мөрийг байгуулна. Энд $w(e)$ гэдгээр of $e$ замын уртыг тэмдэглэв.

Чи хүсэлт бүрт $T(b)$-г хэвлэх ёстой.

Оролт

Эхний мөрөнд $n$ ба $q$ ($2 ≤ n ≤ 10^{5}$; $1 ≤ q ≤ 10^{5}$) тоонууд байна.

Дараагийн мөрөнд $n - 1$ ширхэг $f_{1}, f_{2}, ..., f_{n - 1}$ ($|f_{i}| ≤ 1000$) бүхэл тоонууд зайгаар тусгаарлагдан байна.

Дараагийн $n - 1$ мөрөнд замуудын тайлбар байна. Мөр бүрт $v, u$ ба $w$ гэсэн тоонууд байх ба энэ нь $v$ болон $u$ хотыг $w$ урттай замаар холбосныг илэрхийлнэ ($1 ≤ v, u ≤ n$; $1 ≤ w ≤ 10^{9}$) .

Дараагийн $q$ мөрөнд хүсэлтүүдийг тайлбарлана. Мөр бүрт $v, u, l$ ($1 ≤ v, u ≤ n$, $v ≠ u$ ба $1 ≤ l ≤ 10^{9}$) гэсэн бүхэл тоонууд байрлана.

Гаралт

Хүсэлт бүрийн хариуг нэг мөрөнд хэвлэ.

Орчуулсан: Бат-Од

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

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