Codeforces Round #803 (Div. 2)
2 өдрийн дараа |
Codeforces Round #804 (Div. 2)
8 өдрийн дараа |
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