Codeforces Round #804 (Div. 2)
4 өдрийн дараа |
D. Баавгай ба морин цэрэг
хугацааны хязгаарлалт 3 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Та морь унасан баавгайнуудын эсрэг тулалдахыг хүсэж байна уу? Би ч бас хүсэхгүй байна.
Лимак бол хүрэн баавгай. Тэрээр Беэрландын аймшигтай армийн генерал. Уг армийн хамгийн чухал хэсэг нь мэдээж морин цэрэг юм.
Беэрландын морин цэрэг нь $n$ дайчин болон $n$ морьдоос тогтоно. $i$-дахь дайчин нь $w_{i}$ хүчтэй ба $i$-дахь морь нь $h_{i}$ хүчтэй. Дайчныг түүний морьтой нь хамтад нь нэг нэгж гэж нэрлэнэ. Нэг нэгжийн хүч нь дайчин болон морь хоёрын хүчийг үржүүлсэнтэй тэнцүү байх юм. Морин цэргийн нийт хүч нь бүх $n$ нэгжүүдийн хүчний нийлбэртэй тэнцүү байна. Дайчид болон морьдын сайн хослолт нь үнэхээр хүчирхэг морин цэргийг бий болгох юм.
Анхандаа, $i$-дахь дайчин нь $i$-дахь морьтой байна. Танд $q$ ширхэг асуулт өгөгдөнө. Асуулт бүрийн хувьд 2 дайчин нь бие биетэйгээ морио солих юм.
Генерал Лимак бүх боломжит нөхцөл байдалд бэлэн байх ёстой. Хэрэв дайчид нь тэдгээрийн өөрсдийн морио унах нь зөвшөөрөгдөөгүй бол яах вэ? Асуулт бүрийн дараах хэрэв бид нэг ч дайчин нь өөрийнхөө морьтойгоо хослоогүй байхаар бүх дайчдыг бүх моринд хослуулна гэж үзэхэд үүсэх морин цэргийн боломжит хамгийн их хүчийг олно уу ($n ≥ 2$ бүрийн хувьд үргэлж ядаж ганц зөв хослолт байна.).
Бид дайчныг морьгүй үлдээж болохгүйг анхаарна уу.
Оролт
Эхний мөрөнд зайгаар тусгаарлагдсан 2 бүхэл тоо $n$ болон $q$ ($2 ≤ n ≤ 30 000$, $1 ≤ q ≤ 10 000$) өгөгдөнө.
2-дахь мөрөнд $n$ ширхэг зайгаар тусгаарлагдсан бүхэл тоо $w_{1}, w_{2}, ..., w_{n}$ ($1 ≤ w_{i} ≤ 10^{6}$) өгөгдөнө -- эдгээр нь дайчдын хүчийг илэрхийлнэ.
3-дахь мөрөнд $n$ ширхэг зайгаар тусгаарлагдсан бүхэл тоо $h_{1}, h_{2}, ..., h_{n}$ ($1 ≤ h_{i} ≤ 10^{6}$) өгөгдөнө -- эдгээр нь морьдын хүчийг илэрхийлнэ.
Дараагийн $q$ мөрөнд асуултуудыг дүрсэлнэ. Тэдгээрийн $i$-дахь нь зайгаар тусгаарлагдсан 2 бүхэл тоо $a_{i}$ болон $b_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n$, $a_{i} ≠ b_{i}$)-г агуулна, эдгээр нь морьдоо солих дайчдын индексүүдийг илэрхийлнэ.
Гаралт
Асуултуудын хариултуудыг $q$ мөрөнд хэвлэнэ. $i$-дахь мөрөнд эхний $i$ асуултын дараах морин цэргийн боломжит хамгийн их хүчийг хэвлэнэ.
Орчуулсан: Баатархүү
Жишээ тэстүүд
Оролт
4 2 1 10 100 1000 3 7 2 5 2 4 2 4
Гаралт
5732 7532
Оролт
3 3 7 11 5 3 2 1 1 2 1 3 2 3
Гаралт
44 48 52
Оролт
7 4 1 2 4 8 16 32 64 87 40 77 29 50 11 18 1 5 2 7 6 2 5 6
Гаралт
9315 9308 9315 9315
Тэмдэглэл
Эхний жишээний тодруулга:
Дайчид: 1 10 100 1000
Морьд: 3 7 2 5
Эхний асуултын дараа нөхцөл байдал дараах байдлаар харагдана:
Дайчид: 1 10 100 1000
Морьд: 3 5 2 7
Бид $1*2 + 10*3 + 100*7 + 1000*5 = 5732$-тай болно (энэ хослолтонд ямар ч морьтон өөрийн морьтойгоо хослоогүй байгааг анхаарна уу).
2-дахь асуултын дараа бид анхны нөхцөл байдалдаа очих ба тохиромжтой хослолт нь $1*2 + 10*3 + 100*5 + 1000*7 = 7532$ байна.
2-дахь жишээний тодруулга. Эхний асуултын дараа:
Дайчид: 7 11 5
Морьд: 2 3 1
Оновчтой хослуулалт нь $7*1 + 11*2 + 5*3 = 44$ байна.
2-дахь асуултын дараа оновчтой хослуулалт нь $7*3 + 11*2 + 5*1 = 48$ байна.
Эцэст нь оновчтой хослуулалт нь $7*2 + 11*3 + 5*1 = 52$ байх юм.