Емоції Тето

Вхідні дані

Перший рядок містить одне ціле число $n$ $(1 \leq n \leq 2 \cdot 1 0^{5})$ (1 \le n \le 2 \cdot 10^5) — кількість фрагментів у пісні.

Другий рядок містить $n$ цілих чисел $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n $(- 1 0^{9} \leq a_{i} \leq 1 0^{9})$ (-10^9 \le a_i \le 10^9) — емоційні значення фрагментів.

Кожен з наступних $n - 1$ n-1 рядків містить два цілі числа $u$ та $v$ $(1 \leq u, v \leq n, u \neq = v)$ (1 \le u, v \le n,\ u \ne v) — ребро дерева.

Гарантується, що заданий граф є деревом.

Вихідні дані

Виведіть одне ціле число — максимальний можливий контраст серед усіх виборів центрального фрагмента $v$ .

Приклади

Приклад 1

Loading

Приклад 2

Loading

Примітка

У першому прикладі оптимально обрати фрагмент $v = 4$ v = 4 центральним. Тоді фрагмент $2$ знаходиться на відстані рівно $2$ від нього, тому він видаляється.

Після видалення залишаються дві зв'язані частини:

${1}$ із сумою $1$ ;
${3, 4, 5}$ \{3, 4, 5\} із сумою $3 + 4 + 5 = 12$ 3 + 4 + 5 = 12.

Отже, контраст дорівнює $12 - 1 = 11$ 12 - 1 = 11.

У другому прикладі оптимально обрати фрагмент $v = 2$ v = 2 центральним. Тоді фрагмент $3$ знаходиться на відстані рівно $2$ від нього, тому він видаляється.

Після видалення залишаються три зв'язані частини:

${1, 2, 4, 5}$ \{1, 2, 4, 5\} із сумою $5 + (- 2) + 10 + (- 3) = 10$ 5 + (-2) + 10 + (-3) = 10;
${6}$ із сумою $7$ ;
${7}$ із сумою $- 6$ .

Отже, контраст дорівнює $10 - (- 6) = 16$ 10 - (-6) = 16.

Оцінювання

Підзадача $1$ ( $10$ балів): $n \leq 10$ n \le 10.
Підзадача $2$ ( $30$ балів): $n \leq 5000$ n \le 5000.
Підзадача $3$ ( $30$ балів): дерево є шляхом.
Підзадача $4$ ( $30$ балів): $a_{i} = 1$ a_i = 1 для всіх $1 \leq i \leq n$ 1 \le i \le n.
Підзадача $5$ ( $40$ балів): $∣ a_{i} ∣ \leq 1$ |a_i| \le 1 для всіх $1 \leq i \leq n$ 1 \le i \le n.
Підзадача $6$ ( $40$ балів): $a_{i} \geq 0$ a_i \ge 0 для всіх $1 \leq i \leq n$ 1 \le i \le n.
Підзадача $7$ ( $120$ балів): Без додаткових обмежень.