НВП на дереві#10657
У вас є дерево з вершинами, де -те ребро з'єднує вершини u_i та v_i. На кожній вершині написане ціле число a_i. Для кожного цілого числа від до розв'яжіть наступну задачу:
Сформуйте послідовність, розташувавши цілі числа, записані у вершинах найкоротшого шляху від вершини до вершини , у порядку їх проходження. Знайдіть довжину найбільшої зростаючої підпослідовності цієї послідовності.
Найбільша зростаюча підпослідовність послідовності довжини - це підпослідовність A_{i_1}, A_{i_2}, \ldots, A_{i_m} з найбільшим можливим значенням , що 1 \leq i_1 < i_2 < \ldots < i_m \leq L і A_{i_1} < A_{i_2} < \ldots < A_{i_m}.
Перший рядок містить число (2 \leq n \leq 2 \cdot 10^5). Другий рядок містить числа a_1, a_2, \ldots, a_n (1 \leq a_i \leq 10^9). Кожен з наступних n - 1 рядків містить ребро (u_i, v_i) (1 \leq u_i, v_i \leq n).
Виведіть рядків. У -му рядку виведіть довжину найбільшої зростаючої підпослідовності для послідовності, отриманої з найкоротшого шляху від вершини до вершини .
Приклад 1