Codeforces Round #804 (Div. 2)
00:08:05 |
Educational Codeforces Round 131 (Rated for Div. 2)
5 өдрийн дараа |
Codeforces Round #805 (Div. 3)
7 өдрийн дараа |
Codeforces Round #806 (Div. 4)
9 өдрийн дараа |
E. Дзи мод тарих дуртай
хугацааны хязгаарлалт 3 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Дзи мод тарих дуртай ба модны асуудлуудыг шийдэх нь түүнд гайхалтай байдаг.
Дзид $n$ зангилаанууд ($1$-с $n$ хүртэл дугаарлагдсан) агуулсан жинтэй мод (чиглэлгүй, циклгүй холбоост граф) байна. $x$ ба $y$ зангилаануудын хоорондох хамгийн богино замын хамгийн урт ирмэгийг $g(x, y)$ $(1 ≤ x, y ≤ n)$ функцээр тодорхойлно. Ялангуяа бүх $z$-н хувьд $g(z, z) = 0$ байна.
$p_{1}, p_{2}, ..., p_{n}$ $(1 ≤ p_{i} ≤ n)$ дарааллын бүх бүхэл тоонуудын хувьд нь $f(p)$ функцыг тодорхойлно .
Дзи ийм $p$ дарааллын $f(p)$-д байгаа хамгийн их боломжит утгыг олохыг хүсэж байна. Гэхдээ нэг хязгаарлалт байгаа: $j$ элемент $p$ дараалалд хамгийн ихдээ $x_{j}$ удаа гарч ирж чадна.
Тодорхойлсон хязгаарлалтын хүрээнд байж болох хамгийн их $f(p)$-г олно уу.
Оролт
Эхний мөр нь $n (1 ≤ n ≤ 3000)$ бүхэл тоог агуулна.
Дараагийн $n - 1$ мөр бүр нь $a_{i}, b_{i}, c_{i} (1 ≤ a_{i}, b_{i} ≤ n; 1 ≤ c_{i} ≤ 10000)$ гурван бүхэл тоог агуулах ба $a_{i}$ ба $b_{i}$-н хоорондох $c_{i}$ урттай ирмэгийг илэрхийлнэ. Эдгээр ирмэгүүд нь модны ирмэгүүд гэдэг нь баталгаатай.
Дараагийн $n$ мөр бүр нь $x$ дарааллын элементүүдийг тодорхойлно. $j$-р мөр нь $x_{j} (1 ≤ x_{j} ≤ n)$ бүхэл тоог агуулна.
Гаралт
Хариуг илэрхийлсэн нэг бүхэл тоо хэвлэнэ.
Орчуулсан: Даариймаа
Жишээ тэстүүд
Оролт
4 1 2 1 2 3 2 3 4 3 1 1 1 1
Гаралт
2
Оролт
4 1 2 1 2 3 2 3 4 3 4 4 4 4
Гаралт
3
Тэмдэглэл
In the first sample, one of the optimal $p$ is $[4, 3, 2, 1]$.