Програмчлалын олимпиадын бодлогын архив

Леонардогийн үед хүүхдүүдийн дунд алдартай байсан тоглоом бол Шүр болон Утас тоглоом юм. Тухайн тоглоом нь нэрнээсээ ойлгомжтой маш энгийн шүрнүүд болон утсаар тоглоно. Харин өнгөний хувьд утас нь улаан болон цэнхэр гэсэн 2 янзын өнгөтэй байна. Шүрнүүд 1 - ээс n хүртлэх тоонуудаар дугаарлагдсан. Тоглоом эхлэх үед нэг шүртэй эхлэнэ. Энэ мөчөөс хойш утсыг ашиглан дараах байдлаар шүрнүүдийг тоглоомонд нэмнэ.

•  Append(w,v) – шинэ шүр w нь одоо байгаа шүр v дээр улаан утсаар дамжин залгагдана.
•  Insert(w,u,v) – шинэ шүр w – г оруулахдаа u болон v – г холбоход өмнө нь ашиглагдаж байсан улаан утасны оронд 2 ширхэг шинэ цэнхэр утас ашиглан u болон v хоёр шүрний хооронд шинэ шүрийг оруулна. Өөрөөр хэлбэл өмнө нь байсан u – v улаан утас нь хоёр шинэ цэнхэр утас болох u – w болон w – v гэсэн утсуудаар солигдоно гэсэн үг.

Утасны (улаан болон цэнхэр) хэсэг бүр нь өөрийн гэсэн тодорхой урттай. Тоглоом дуусахад цэнхэр утасны уртыг л тоолно (улаан утасны уртыг тоолохгүй). Энэ уртыг тоглолтын нийт оноо гэж нэрлэнэ.
Танд шүр болон утас тоглоомын эцсийн байрлалыг дараах байдлаар өгсөн: шүрнүүд хоорондоо хэрхэн холбогдож байгаа, холбосон утасуудын урт байх ба харин өнгө нь өгөгдөхгүй.
Таны даалгавар бол өгөгдсөн байрлалын хувьд боломжтой хамгийн их нийт оноог олох програм бичих явдал юм. Өөрөөр хэлбэл тухайн өгөгдсөн байрлалд тохирох боломжит тоглолтуудаас хамгийн их эцсийн оноотойг (цэнхэр утаснуудын уртын нийлбэр) нь олж тэр оноог гаргах юм.
Оролт
Эхний мөрөнд n гэсэн эерэг бүхэл тоо өгөгдөх ба энэ нь тоглоом дахь нийт шүрний тоо юм. Шүрнүүд нь 1 – ээс n хүртлэх тоонуудаар дугаарлагдсан байна. Дараагийн n-1 мөр тус бүрд гурван тоо байна: ai, bi (1 ≤ ai < bi ≤ n) болон ci (1≤ ci ≤ 10000) – хоорондоо холбогдсон хоёр шүрний дугаарууд болон холбосон утасны урт.
Гаралт
Гаралт нь бүхэл тоо байна – тоглоомын боломжит хамгийн их нийт оноо
Жишээ

Оролт

5
1 2 10
1 3 40
1 4 15
1 5 20

Гаралт

60

Оролт

10
4 10 2
1 2 21
1 3 13
6 7 1
7 9 5
2 4 3
2 5 8
1 6 55
6 8 34

Гаралт

140

Тайлбар
Жишээний эхний тохиолдолд, нийт оноо нь 60 бөгөөд дараах байдлаар гарч ирсэн. 3 гэсэн ганц шүрнээс эхлэнэ.

•  Шүр 5 – ыг 3 руу залгах (дурын урттай утсаар)
•  Шүр 1 – ийг 3-5 хооронд оруулах (оруулж байгаа учраас 40 болон 20 гэсэн урттай утсыг ашиглана)
•  Шүр 2 –ыг 1 рүү залгахдаа 10 урттай утсыг ашиглана
•  Шүр 4 –ийг 1 рүү залгахдаа 15 урттай утсыг ашиглана

Үр дүн дараах байдалтайгаар гарах ба өөр ямар нэг аргаар илүү өндөр нийт оноо авах боломжгүй нь (өнгийг тооцохгүй бол) харагдаж байна.

2 дахь тестийн үр дүнд тоглоомын нийт оноо нь доорх зурагт үзүүлсэн байдлаар 140 оноо гэж гарсан байна.