Masala #L4TGRC5IH7

Qadimiy bog‘da \(n\) ta haykal joylashgan bo‘lib, ular yo‘laklar orqali daraxtsimon shaklda ulangan. Har bir haykalning estetik qiymati mavjud (musbat yoki manfiy bo‘lishi mumkin).

Bog‘bon bir nechta haykallarni tanlab, ko‘rgazma tashkil qilmoqchi. Biroq, xavfsizlik sababli yonma-yon joylashgan haykallarni birga tanlash mumkin emas.

Bog‘bon sizdan yordam so‘raydi:

Qaysi haykallarni tanlash kerakki, ularning umumiy estetik qiymati maksimal bo‘lsin?

Birinchi qatorda, \(n\), \((1 ≤ n ≤ 2·10^5)\). 

Keyingi qatorda \(n\) butun \(w[i]\), \((|w[i]| ≤ 10^9)\). 

Keyingi qatorda \(n-1\) ta yo'lak: \(u,v\)

Maksimal umumiy qiymat