D. Алимны мод

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

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

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

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

Танд $n$ оройтой үндэстэй мод өгөгджээ. Модны навч орой бүрт(1 зэрэгтэй орой) энэ орой дахь алимны тоог харгалзуулжээ.

Дэд модны навчнууд дээрх бүх тоонуудын нийлбэрийг энэ дэд модны жин гэе.

Модны $v$ орой бүрийн хувьд $v$-н хүүхдүүдэд харгалзах дэд моднууд нь адил жинтэй байвал уг модыг тэнцвэрт мод гэе.

Модыг тэнцвэрт болгохын тулд хамгийн цөөндөө хэдэн ширхэг алимыг үүнээс салгах хэрэгтэй болохыг тооцоол. Ядахнаа бүх алимыг нь аваад зорилгодоо хүрч болохыг санаарай.

Оролт

Эхний мөрөнд модны оройн тоо болох $n (2\le n\le 10^5)$ бүхэл тоо өгөгдөнө.Дараагийн мөрөнд $ a_1,a_2,...,a_n (0\le a_i\le 10^8)$ тоонууд өгөгдөнө:$a_i$ нь $i$ дэх орой дахь алимны тооо. Навч биш оройнуудын хувьд тэг байна.

Дараагийн $n - 1$ мөрнүүд модны ирмэгүүдийг тодорхойлно. Мөр бүр нь $x_i,y_i (1\le x_i,y_i\le n,x_i\not=y_i)$ бүхэл тоон агуулах ба энэ ирмэгээр холбогдсон оройнуудыг илтгэнэ. Оройнууд $1$-с $n$ хүртэл дугаарлагдсан ба үндэс нь $1 $ дугаартай байна.

Гаралт

Модыг тэнцвэрт болгохын тулд хамгийн цөөндөө хэдэн ширхэг алим авах ёстойг илэрхийлэх ганц тоог хэвлэ.

Жич: С++ хэл хэрэглэж байгаа бол 64-бит бүхэл тоог уншихдаа %lld тодорхойлогчийг ашиглахгүй байхыг зөвлөж байна. cin, cout стриймүүд эсвэл %I64d тодорхойлогчийг ашиглана уу.

Орчуулсан: Төрбат

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

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