Значення в кореневому дереві

Обмеження: 3 сек., 512 МіБ

Вам задано кореневе дерево з \(n\) вершинами. Вершини пронумеровані від \(1\) до \(n\), а коренем є вершина \(1\). \(i\)-те ребро з’єднує вершини \(u_i\) та \(v_i\). У вершині \(v\) записано ціле число \(a_v\).

Для кожної вершини \(v\) знайдіть максимальне значення \(m\), для якого існує таке число \(x\), що всі значення \(x, x + 1, \dots, x + m - 1\) присутні на шляху від кореня до вершини \(v\).

Вхідні дані

У першому рядку задано ціле число \(n\) — кількість вершин дерева.

У другому рядку задано \(n\) цілих чисел \(a_v\), записаних у вершинах дерева.

У наступних \(n - 1\) рядках задано по два цілі числа \(u_i\), \(v_i\) — кінці \(i\)-го ребра.

Вихідні дані

В одному рядку виведіть \(n\) цілих чисел — максимальне значення \(m\) для кожної вершини \(v\), де \(1 \le v \le n\).

Обмеження

\(1 \le n \le 3 \cdot 10^5\),

\(0 \le a_v \le 10^9\),

\(1 \le u_i, v_i \le n\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
5 2 4 0 3 5 1 2 1 3 2 4 2 5	1 1 1 3 2

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
7 1 3 2 2 0 11 10 4 5 5 1 2 5 2 3 1 6 7 6	1 2 4 3 2 1 2

Примітки

У першому прикладі відповіді для всіх вершин є такими.

• Вершина \(1\). Оскільки коренем є вершина \(1\), шлях від кореня до вершини \(1\) містить лише одну вершину. У цьому випадку \(m = 1\).

• Вершина \(2\). Шлях від кореня до вершини \(2\) містить дві вершини — \(1\) та \(2\) — зі значеннями \(2\) та \(4\) відповідно. Знову ж таки, \(m = 1\).

• Вершина \(3\). Шлях від кореня до вершини \(3\) містить дві вершини — \(1\) та \(3\) — зі значеннями \(2\) та \(0\) відповідно. Для вершини \(3\) відповідь дорівнює \(m = 1\).

• Вершина \(4\). Шлях від кореня до вершини \(4\) містить три вершини — \(1\), \(2\) та \(4\) — зі значеннями \(2\), \(4\) та \(3\) відповідно. У цьому випадку відповідь дорівнює \(m = 3\), оскільки для \(x = 2\) на шляху присутні значення \(x = 2\), \(x + 1 = 3\) та \(x + 2 = 4\).

• Вершина \(5\). Шлях від кореня до вершини \(5\) містить три вершини — \(1\), \(2\) та \(5\) — зі значеннями \(2\), \(4\) та \(5\) відповідно. У цьому випадку відповідь дорівнює \(m = 2\), оскільки для \(x = 4\) на шляху присутні значення \(x = 4\) та \(x + 1 = 5\).