НВП на дереві
У вас є дерево з 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.