AĞACDA NVP

Verilmiş ağacda n zirvə var və hər bir i-ci qıraq u[i] zirvəsini v[i] zirvəsi ilə birləşdirir. Hər zirvədə i tam ədədi a[i] yazılıb. 1-dən n-ə qədər olan hər bir tam ədəd k üçün aşağıdakı tapşırığı yerinə yetirin:

Zirvə 1-dən zirvə k-ya qədər olan ən qısa yolda zirvələrdə yazılmış tam ədədləri görünmə sırasına görə düzün və bu ardıcıllığın ən uzun artan alt ardıcıllığının uzunluğunu tapın.

Burada L uzunluğunda A ardıcıllığının ən uzun artan alt ardıcıllığı, 1 ≤ i[1] < i[2] < ... < i[m] ≤ L və A[i1] < A[i2] < ... < A[im] şərtini ödəyən ən böyük mümkün m dəyərinə malik olan A[i1], A[i2], ..., A[im] alt ardıcıllığıdır.

Giriş məlumatları

Birinci sətir n ədədini (2 ≤ n ≤ 2 * 10^5) ehtiva edir. İkinci sətir a[1], a[2], ..., a[n] ədədlərini (1 ≤ a[i] ≤ 10^9) ehtiva edir. Növbəti n - 1 sətirin hər biri bir qırağı (u[i], v[i]) (1 ≤ u[i], v[i] ≤ n) ehtiva edir.

Çıxış məlumatları

n sətir çıxarın. k-cı sətirdə zirvə 1-dən zirvə k-ya qədər olan ən qısa yoldan alınan ardıcıllığın ən uzun artan alt ardıcıllığının uzunluğunu çıxarın.