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

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

3 секунди
512 мегабайтів
Складна

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

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

Вхідні дані

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

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

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

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

0 \le a_v \le 10^9,

1 \le u_i, v_i \le n.

Вихідні дані

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

Приклади

Приклад

Loading
Loading

Приклад 1

Loading
Loading

Примітка

Перший приклад

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

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

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

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

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

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

Другий приклад