D. Мод

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

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

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

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

Бяцхан X-д $n$ зангилаанаас ($1$-с $n$ хүртэл дугаарлагдсан) бүрдсэн мод байв. Модны ирмэг бүр нь эерэг бүхэл тоо байна. $v$, $u$ хоёр зангилааны хоорондын зайг (бид үүнийг $d(v, u)$ илэрхийлье) $v$ ба $u$ хоёрын хоорондох хамгийн богино замын ирмэгүүдийн уртын нийлбэрээр тодорхойлно.

$p$ сэлгэмэл нь $n$ ялгаатай бүхэл тооны дараалал $p_{1}, p_{2}, ..., p_{n}$ $(1 ≤ p_{i} ≤ n)$ юм. Бяцхан X нь $p$ сэлгэмэлийн боломжит хамгийн их нийлбэрийг олохыг хүсэж байна. Хэрвээ тохиромжтой олон сэлгэмэл байгаа бол тэр цагаан толгойн дарааллаар хамгийн багийг нь хайна. Даалгаврыг биелүүлэхэд нь түүнд туслана уу!

Оролт

Эхний мөр нь $n (1 ≤ n ≤ 10^{5})$ бүхэл тоог агуулна.

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

Модонд эдгээр ирмэгүүд баталгаатай байна.

Гаралт

Эхний мөрөнд тодорхойлогдсон нийлбэрийн хамгийн их боломжтой утгыг хэвлэнэ. Хоёр дахь мөрөнд цагаан толгойн дарааллаар хамгийн бага сэлгэмэлийг төлөөлсөн $n$ бүхэл тоонуудыг хэвлэнэ.

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

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

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