Գումար և արտադրյալ

Առաջին տողը պարունակում է մեկ ամբողջ թիվ $n$ $(2 \leq n \leq 100000)$ (2 \leq n \leq 100\,000), որը ցույց է տալիս քաղաքների քանակը:

Երկրորդ տողը պարունակում է $n$ ամբողջ թվեր $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n $(1 \leq a_{i} \leq 1 0^{9})$ (1 \leq a_i \leq 10^9), որտեղ $a_{i}$ a_i-ն ցույց է տալիս $i$ -րդ քաղաքի ոսկու քանակը:

Հաջորդ $n - 1$ n-1 տողերից յուրաքանչյուրը պարունակում է երկու ամբողջ թվեր $u$ և $v$ $(1 \leq u, v \leq n, u \neq = v)$ (1 \leq u, v \leq n, u \neq v), որոնք ցույց են տալիս, որ կա ճանապարհ $u$ և $v$ քաղաքների միջև:

Գումար և արտադրյալ

Examples