НВП на дереве
Задано дерево с n вершинами, i - ое ребро которого соединяет вершину u[i] и вершину v[i]. На вершине i написано целое число a[i]. Для каждого целого числа k от 1 до n решите следующую задачу:
Составим последовательность, выстроив целые числа, записанные в вершинах кратчайшего пути от вершины 1 до вершины k, в порядке их появления. Найдите длину наибольшей возрастающей подпоследовательности этой последовательности.
Здесь наибольшая возрастающая подпоследовательность последовательности A длины L - это подпоследовательность A[i1], A[i2], ..., A[im] с таким наибольшим возможным значением m, что 1 ≤ i[1] < i[2] < ...< i[m] ≤ L и A[i1] < A[i2] < ... < A[im].
Входные данные
Первая строка содержит число n (2 ≤ n ≤ 2 * 10^5). Вторая строка содержит числа a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ 10^9). Каждая из следующих n - 1 строк содержит ребро (u[i], v[i]) (1 ≤ u[i], v[i] ≤ n).
Выходные данные
Выведите n строк. В k - ой строке выведите длину наибольшей возрастающей подпоследовательности для последовательности, полученной из кратчайшего пути от вершины 1 до вершины k.
