C. Мод ба массив

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

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

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

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

Хэрэглэгч Айнта моднуудад дуртай. Энэ удаад тэр $1$-с $n$ хүртэл дугаарлагдсан $n$ оройтой чиглэлгүй мод хийх гэж байна. Мод нь жинтэй, тиймээс модны ирмэг бүр ямар нэгэн бүхэл тоон жинтэй.

Мөн түүнд $t$ массив байна: $t[1], t[2], ..., t[n]$. Эхлээд массивын бүх элементүүд $0$ байна. Дараа нь модны $u$ ба $v$ ($u < v$) оройнуудыг холбосон $c$ жинтэй ирмэгийн хувьд $t$ массивын $t[u], t[u + 1], ..., t[v - 1], t[v]$ элементүүдийг $c$ утгаар нэмэгдүүлнэ.

$d(u, v)$ бол $u$ ба $v$ оройнуудын хоорондох хамгийн богино замын ирмэгүүдийн нийт жин гэж үзье. Хэрвээ $d(x, y) = t[x] + t[x + 1] + ... + t[y - 1] + t[y]$ бол хэрэглэгч Айнта $x, y$ ($1 ≤ x < y ≤ n$) бүхэл тоон хосыг сайн гэж дууддаг.

Хэрэглэгч Айнта наад зах нь сайн хосууд хийхийг хүссэн боловч тэр зөв модыг хийж чадахгүй байна. Айнтад ийм мод олоход нь тусал.

Оролт

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

Гаралт

Ирмэгүүдийн тодорхойлолтыг агуулсан $n - 1$ мөрүүд хэвлэнэ. $i$-р мөр нь зайгаар тусгаарлагдсан гурван бүхэл $u_{i}, v_{i}, c_{i}$ ($1 ≤ u_{i} < v_{i} ≤ n; 1 ≤ c_{i} ≤ 10^{5}$) тоонуудыг агуулна. Эдгээр нь ирмэгээр холбогдсон хоёр орой болон ирмэгийн жин юм.

Дараа нь мөрүүдэд сайн хосуудыг хэвлэнэ. $k$-р мөр нь зайгаар тусгаарлагдсан хоёр бүхэл $x_{k}$, $y_{k}$ ($1 ≤ x_{k} < y_{k} ≤ n$) тоонуудыг агуулна. Мэдээж хэрэг $x_{k}, y_{k}$ сайн хосууд байх ёстой. , $x_{j} ≠ x_{k}$, $y_{j} ≠ y_{k}$ эдгээр бүх хосууд ялгаатай байх ёстой.

Хэрвээ олон зөв шийд байгаа бол тэдгээрээс аль нэгийг нь хэвлэнэ.

Орчуулсан: Даариймаа

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

Оролт
7
Гаралт
1 4 1
1 2 2
2 3 5
3 5 3
2 6 2
6 7 3
4 5
5 6
5 7

Тэмдэглэл

$⌊x⌋$ бол $x$-ээс ихгүй хамгийн их бүхэл тоо.

Чи модны тодорхойлолтыг дараах холбоосоор олж болно: http://en.wikipedia.org/wiki/Tree_(graph_theory)$

Чи хамгийн богино замын тодорхойлолтыг дараах холбоосоор олж болно: http://en.wikipedia.org/wiki/Shortest_path_problem$

Мод болон $t$ массивын жишээний гаралт үүн шиг харагдана:

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