D. Цагаан ба Хар мод

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

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

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

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

Самбар дээр $n$ зангилаанаас бүрдэх мод хэлбэрийн граф (зангилаа болон шулуунаас бүрдсэн) зурагдсан байна. Чиглэлгүй граф нь хэрвээ хоорондоо холбогдсон ба ямар нэгэн цикл агуулаагүй бол мод гэж нэрлэдэг.

Графийн зангилаа бүр цагаан эсвэл хар өнгөөр будагдсан байх ба шулуунаар холбогдсон хоёр зангилаа ижил өнгөтэй байж болохгүй. Шулуун бүр эерэг бүхэл тоон утга агуулна.

Сахилгагүй жаал Вася самбар дээр ирэх ба $s_{v}$ тоог $v$ зангилаа бүрийн ойролцоо бичих бөгөөд энэ тоо нь зангилаанд холбоотой байсан шулуунуудын утгуудын нийлбэр байна. Дараа нь Вася самбараас шулуунуудыг тэдний утгуудтай хамт арилгана.

Таны ажил бол эх модыг зангилааны өнгө болон $s_{v}$ тоонуудаас сэргээх юм.

Оролт

Эхний мөрөнд нэг ширхэг бүхэл тоо $n$ ($2 ≤ n ≤ 10^{5}$) байх ба энэ нь модны зангилааны тоо юм. Дараагийн $n$ мөрөнд нэг зайгаар тусгаарлагдсан хос бүхэл тоон утгууд $c_{i}$, $s_{i}$ ($0 ≤ c_{i} ≤ 1$, $0 ≤ s_{i} ≤ 10^{9}$) байх ба $c_{i}$ нь самбар дээр зурагдсан модны $i$-р зангилааны өнгө (0 бол цагаан 1 бол хар өнгийг илтгэнэ), $s_{i}$ нь $i$-р зангилаанд холбогдсон шулуунууд дээр байсан утгуудын нийлбэр юм.

Гаралт

Мод графын $n-1$ шулууны тодорхойлолтыг хэвлэ. Тодорхойлолт бүр гурван ширхэг бүхэл тоон утгуудаас $v_{i}$, $u_{i}$, $w_{i}$ ($1 ≤ v_{i}, u_{i} ≤ n$, $v_{i} ≠ u_{i}$, $0 ≤ w_{i} ≤ 10^{9}$) бүрдэх ба $v_{i}$ болон $u_{i}$ нь $i$ шулуунаар холбогдсон зангилаануудын дугаар ба $w_{i}$ нь $i$ шулууны утга болно. Мөн $c_{v_{i}} ≠ c_{u_{i}}$ нөхцөл биелэж байх ёстой.

Энэ нь оролтын өгөгдөл бүрт өгөгдөлтэй таарах дор хаяж нэг граф оршино гэсэн үг юм. Хэрвээ олон шийдэл байвал алийг нь ч хэвлэж болно. Гаралтын шулуунуудыг хэвлэхдээ ямар ч дарааллаар хэвлэж болно. Тоонуудыг хэвлэхдээ зайгаар тусгаарлан хэвлэнэ үү.

Орчуулсан: Г.Мэндбаяр

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

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