E. Функционал граф дээрх маршрутын анализ

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

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

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

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

Танд нэгэн функционал граф өгөгджээ. Уг граф нь чиглэлтэй граф байх бөгөөд орой болгоноос яг нэг ширхэг нум гарч байв. Мөн оройнууд нь 0-ээс $n - 1$ хүртэл дугаарлагдсан байна.

Граф нь $f_{0}, f_{1}, ..., f_{n - 1}$ гэсэн цуваа хэлбэртэйгээр өгөгдөх ба энд $f_{i}$ нь $i$-дахь оройгоос гарч буй цорын ганц нум нь очих оройн дугаарыг илэрхийлэх юм. Түүнчлэн танд $w_{0}, w_{1}, ..., w_{n - 1}$ гэсэн нумуудын жингүүдээс тогтох цуваа өгөгдөх ба энд $w_{i}$ нь $i$-дахь оройгоос $f_{i}$ гэсэн дугаартай орой хүрэх нумын жинг илэрхийлнэ.

Уг зурагт эхний жишээний граф-ыг дүрслэв.

Мөн танд бүхэл тоо $k$ (маршрутын урт) өгөгдөх ба та орой болгоны хувьд $s_{i}$ and $m_{i}$ гэсэн 2 тоог олох хэрэгтэй бөгөөд эдгээр тоонуудын тайлбар доор өгөгдөв:

  • $s_{i}$ -- $i$-дахь оройгоос эхлэх $k$ урттай маршрутын бүх нумуудын жингүүдийн нийлбэр;
  • $m_{i}$ -- $i$-дахь оройгоос эхлэх $k$ урттай маршрутын бүх нумуудын жингүүдийн хамгийн бага жин.

Маршрутын урт гэдэг нь уг маршрут дээрх нумуудын тоотой тэнцүү байх юм.

Оролт

Эхний мөрөнд 2 бүхэл тоо $n, k$ ($1 ≤ n ≤ 10^{5}, 1 ≤ k ≤ 10^{10}$) өгөгдөнө. 2-дахь мөрөнд $f_{0}, f_{1}, ..., f_{n - 1}$ ($0 ≤ f_{i} < n$) дараалал өгөгдөх ба 3-дахь мөрөнд $w_{0}, w_{1}, ..., w_{n - 1}$ ($0 ≤ w_{i} ≤ 10^{8}$) дараалал өгөгдөнө.

Гаралт

$n$ ширхэг мөр хэвлэх ба мөр болгонд $s_{i}$, $m_{i}$ гэсэн хос бүхэл тоонуудыг хэвлэсэн байна.

Орчуулсан: Баатархүү

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

Оролт
7 3
1 2 3 4 3 2 6
6 3 1 4 2 2 3
Гаралт
10 1
8 1
7 1
10 2
8 2
7 1
9 3
Оролт
4 4
0 1 2 3
0 1 2 3
Гаралт
0 0
4 1
8 2
12 3
Оролт
5 3
1 2 3 4 0
4 1 2 14 3
Гаралт
7 1
17 1
19 2
21 3
8 1
Сэтгэгдлүүдийг ачааллаж байна...