НВП на дереве
НВП на дереве
Задано дерево с n вершинами, i - ое ребро которого соединяет вершину ui
и вершину vi
. На вершине i написано целое число ai
. Для каждого целого числа k от 1 до n решите следующую задачу:
Составим последовательность, выстроив целые числа, записанные в вершинах кратчайшего пути от вершины 1 до вершины k, в порядке их появления. Найдите длину наибольшей возрастающей подпоследовательности этой последовательности.
Здесь наибольшая возрастающая подпоследовательность последовательности A длины L - это подпоследовательность Ai1
, Ai2
, ..., Aim
с таким наибольшим возможным значением m, что 1 ≤ i1
< i2
< ...< im
≤ L и Ai1
< Ai2
< ... < Aim
.
Входные данные
Первая строка содержит число n (2 ≤ n ≤ 2 * 105
). Вторая строка содержит числа a1
, a2
, ..., an
(1 ≤ ai
≤ 109
). Каждая из следующих n - 1 строк содержит ребро (ui
, vi
) (1 ≤ ui
, vi
≤ n).
Выходные данные
Выведите n строк. В k - ой строке выведите длину наибольшей возрастающей подпоследовательности для последовательности, полученной из кратчайшего пути от вершины 1 до вершины k.
10 1 2 5 3 4 6 7 3 2 4 1 2 2 3 3 4 4 5 3 6 6 7 1 8 8 9 9 10
1 2 3 3 4 4 5 2 2 3