Танд n оройтой мод өгөгдөнө. Орой бүр жимсний тоотой.

Хэрвээ та нэг оройг сонговол түүний шууд хөрш (эцэг/хүүхэд) оройг сонгож болохгүй.

Хамгийн их жимс ол.

Оролт:

n

a[i]

Дараагийн n-1 мөр: ирмэгүүд u v

Гаралт:

Гаралтын файлд Хамгийн их жимс

Хязгаарлалтууд:

• \(1 ≤ n ≤ 10^5\)
• \(0 ≤ a[i] ≤ 10^4\)

Дэд бодлого

Жишээ:

Оролт-1

3
3 2 3
1 2
1 3

Гаралт-1

5

Оролт-2

4
3 4 5 1
1 2
1 3
3 4

Гаралт-2

9