Досвід#8724

Досвід

0,5 секунди

256 мегабайтів

Складна

Компанія X має $N$ працівників. Вона організована у вигляді дерева з суворою ієрархією: генеральний директор (CEO) знаходиться на вершині (корінь дерева), у нього є певна кількість прямих підлеглих, які також мають своїх підлеглих, і так далі, аж до звичайних працівників, які не мають підлеглих (листи дерева). Працівники пронумеровані від $1$ до $N$ . Генеральний директор має номер 1, але інші номери не відображають ієрархію. Кожен працівник має певний досвід – $i$ -й працівник має досвід, позначений невід'ємним цілим числом $W_{i}$ W_i.

Компанія має багато групових проектів, і керівництво вирішило розподілити всіх працівників на різні групи (команди), щоб виконати наступні умови:

Кожна команда повинна складатися щонайменше з однієї особи, і кожна особа повинна належати рівно до однієї команди.
Кожна команда повинна складатися лише з людей, які є послідовними підлеглими один одного. Група працівників $j_{1}$ j_1, $j_{2}$ j_2, $j_{3}$ j_3, $j_{4}$ j_4 … є допустимою командою, якщо $j_{2}$ j_2 є прямим підлеглим $j_{1}$ j_1, $j_{3}$ j_3 є прямим підлеглим $j_{2}$ j_2, $j_{4}$ j_4 є прямим підлеглим $j_{3}$ j_3 і так далі.

Керівництво знає, що після завершення групового проекту загальний досвід групи, призначеної на проект, збільшується на $W_{ma x} - W_{min}$ W_{max} - W_{min}, де $W_{ma x}$ W_{max} – це максимальний досвід, а $W_{min}$ W_{min} – це мінімальний досвід серед членів групи. Загальне збільшення досвіду для компанії дорівнює сумі збільшень досвіду всіх команд. Керівництво хоче максимізувати загальне збільшення досвіду для компанії, розділивши працівників на найкращу можливу конфігурацію команд, дотримуючись двох вищезгаданих умов.

Напишіть програму experience для обчислення максимального можливого збільшення досвіду для компанії.

Вхідні дані

Перша строка стандартного вводу містить одне ціле число $N$ - кількість працівників у компанії ( $1 \leq N \leq 1 0^{5}$ 1 \leq N \leq 10^5).

Друга строка містить $N$ розділених пробілами невід'ємних цілих чисел $W_{1}, W_{2}, \dots, W_{N}$ W_1, W_2, \ldots, W_N – досвід кожного працівника компанії ( $0 \leq W_{i} \leq 1 0^{9}$ 0 \leq W_i \leq 10^9).

Далі йдуть $N - 1$ N-1 строк, кожна з яких містить розділені пробілами цілі числа $u$ та $v$ у зазначеному порядку. Ці числа представляють підлеглі відносини в компанії – працівник з номером $v$ є прямим підлеглим працівника з номером $u$ .

Вихідні дані

Програма повинна вивести на стандартний вихід одне ціле число – максимальне загальне збільшення досвіду для компанії.

Приклади

Приклад 1

Примітка

Одна з можливих конфігурацій, яка максимізує загальне збільшення досвіду, це {1, 5, 3}, {6, 2, 4}, {7}.

Існує інша конфігурація з тим самим максимальним загальним збільшенням досвіду – {1, 5}, {3}, {6, 2, 4}, {7}.