F. Трийлэнд аялал

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

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

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

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

"Road Accident" хамтлаг Трийлэндийг тойрон урьд өмнө нь байгаагүй аялал хийхээр төлөвлөж байна. RA-н фэнүүд тоглолтыг хүсэн хүлээж байгаа ба тэдний дуртай хамтлаг хэдэн тоглолт хийх вэ гэдэг дээр бооцоо тавьсан.

Трийлэнд $n$ хотоос бүрдэх ба зарим хос хотууд хос чиглэлтэй замаар холбогдсон. Бид дурын хотоос дурын өөр нэг хотруу очих боломжтой эсэхийг мэднэ. Хотууд $1$-c $n$ хүртэлх бүхэл тоогоор дугаарлагдсан. Хот бүрийн хувьд бид хүн амыг илтгэх $r_{i}$ утгыг мэднэ.

Хамтлаг нэг замын дагуу аялах ба замын дагуух зарим хотуудад л тоглолтоо хийнэ гэдгийг бид мэднэ. Хамтлагийн маршрут нэг хотоор хоёр удаа дайрахгүй ба тэд хөдлөх бүртээ өмнө нь очоогүй хотруу явна.

Хамтлаг аялалын үеэр бүх том цэнгэлдэхүүд болон тоглолтын танхимуудыг олж авахаар төлөвлөж байгаа ба тэд өмнө нь очсон хотын хүн амаас их хүн амтай хотод тоглолтоо хийнэ. Өөрөөр хэлбэл тоглолт хийх хотуудын хүн амын дараалал эрс ихэссэн байна.

Саяхны нэгэн ярилцлагад "road accident" хамтлагийн ахлагч фенүүддээ хамтлаг боломжит хамгийн их хотод тоглолтоо хийнэ гэж амласан. Иймээс хамтлаг Трийлэндийн хэд хэдэн хотуудыг холбосон замаар аялах ба зарим хотуудад л тоглолтоо хийнэ мөн хүн амын тоо өсөх дарааллаар явагдана, тоглолтуудын тоо боломжит хамгийн их байна.

Трийлэндийн хөгжөөн дэмжигчид Трийлэндэд хэдэн тоглолт болохыг тооцоолохоор ухаан мэдрэлгүй оролдож байна. Тэд жинхэнэ програмчлагчын тусламжгүйгээр энэ асуудлыг шийдэж чадахааргүй харагдаж байна. Хөгжөөн дэмжигчдэд олох гэж буй тоглолтуудын тоог олоход туслана уу.

Оролт

Оролтын эхний мөрөнд бүхэл тоон утга $n$ ($2 ≤ n ≤ 6000$) байх буюу Трийлэндийн хотуудын тоо юм. Дараагийн мөрөнд $n$ бүхэл тоон утга $r_{1}, r_{2}, ..., r_{n}$ ($1 ≤ r_{i} ≤ 10^{6}$) байх ба энд $r_{i}$ нь $i$-р хотын хүн ам байна. Дараагийн $n - 1$ мөрөнд замуудын тодорхойлолт байх ба нэг мөрөнд нэг зам байна. Зам бүр хоёр бүхэл тоон утга $a_{j}$, $b_{j}$ ($1 ≤ a_{j}, b_{j} ≤ n$)-р тодорхойлогдох буюу $i$-р замаар холбогдсон хотуудын дугаар байна. Мөрөн дахь бүх тоонууд зайгаар тусгаарлагдана.

Гаралт

"Road Accident" хамтлагийн тоглолтоо хийх хотуудын тоог хэвлэ.

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

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

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