Codeforces Round #803 (Div. 2)
20:09:50 |
Codeforces Round #804 (Div. 2)
6 өдрийн дараа |
E. Миша ба хамгийн урт ерөнхий угтвар
хугацааны хязгаарлалт 8 секунд
санах ойн хязгаарлалт 512 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Мишад оройнууд дээр нь тэмдэгт бичсэн мод байжээ. Тэрээр $s$ болон $t$ оройнуудыг сонгон $s$-ээс $t$-рүү очих замд дайралдах тэмдэгтүүдийг бичжээ. Бид үүнийг $(s, t)$ хосд харгалзах тэмдэгт мөр гэж нэрлэнэ.
Мишад $m$ хүсэлт байгаа: чамд $a$, $b$, $c$, $d$ гэсэн $4$ орой өгөгднө; чи $(a, b)$ ба $(c, d)$ хосуудад харгалзах тэмдэгт мөрүүдийн Хамгийн Урт Ерөнхий Угтварын уртыг олох ёстой.
Оролт
Эхний мөрөнд модны оройн тоо болох $n$ ($1 ≤ n ≤ 300000$) байрлана.
Дараагийн мөрөнд Англи цагаан толгойн $n$ ширхэг үсэг зайгаар тусгаарлагдан байрлана. $i$ дэх тэмдэгт нь $i$ дэх оройд харгалзана.
Дараагийн $n - 1$ мөрөнд ирмэгүүдийг тодорхойлно. Ирмэг нь $u$, $v$ ($1 ≤ u, v ≤ n$, $u ≠ v$) гэсэн зайгаар тусгаарлагдсан хос бүхэл тоогоор тодорхойлогдоно.
Дараагийн мөрөнд хүсэлтийн тоог илэрхийлэх $m$ ($1 ≤ m ≤ 1000000$) бүхэл тоо байрлана.
Дараагийн $m$ мөрөнд хүсэлтүүдийн талаар мэдээлэл байна. Хүсэлт бүр зайгаар тусгаарлагдсан $a$, $b$, $c$, $d$ ($1 ≤ a, b, c, d ≤ n$) дөрвөн бүхэл тоог агуулна.
Гаралт
Хүсэлтүүдийн хариуг буюу хамгийн урт ерөнхий угтварын уртыг нэг нэг мөрөнд хэвлэнэ.
Орчуулсан: Бат-Од
Жишээ тэстүүд
Оролт
6 bbbabb 2 1 3 2 4 3 5 2 6 5 6 2 5 3 1 1 5 2 3 5 6 5 6 6 3 4 1 6 2 3 4 2 2 4 5
Гаралт
2 2 2 0 1 0