Masala E

N ta tugundan tashkil topgan daraxt mavjud. $i-$yo'l $u_i$ va $v_i$ tugunlarni o'zaro bog'laydi va qiymati $a_i$ ga teng. 1 dan N gacha bo'lgan har bir k butun soni uchun quyidagini aniqlang:

• Yo'llarga yozilgan butun sonlarni 1-yo'ldan k-yo'lgacha bo'lgan eng qisqa yo'l bo'ylab ular paydo bo'ladigan tartibda qatorlab ketma-ketlik hosil qilamiz.  Ushbu ketma-ketlikning eng uzun ortib boruvchi pastki ketma-ketligi (LIS)ining uzunligini toping.

Bu yerda uzunligi $L$ boʻlgan $A$ ketma-ketlikning eng uzun ortib boruvchi pastki ketma-ketligi $M$ ning mumkin boʻlgan eng katta qiymatiga ega boʻlgan $A_{i_1}$ ,$A_{i_2}$ ,...,$A_{i_M}$ qatori boʻlib, $1≤i_1 <i_2 <...<i_M ≤L$ va $A_{i_1} < A_{i_2} <...< A_{i_M}$ bo'ladi.

Birinchi qatorda N butun soni kiritiladi.

Keyingi qatorda N ta butun son a massiv elementlari kiritiladi

Keyingi N-1 ta qatorning har birida 2 tadan butun son $u_i$ va $v_i$ kiritiladi.

• $2 \le N \le 2*10^5$
• $1 \le a_i \le 10^9$
• $1 \le u_i, v_i \le N$
• $u_i \neq v_i$
• Graf daraxt ekanligi kafolatlanadi.
• Barcha qiymatlar butun sonlardir.

N qatorni chop eting.  k-chi qator, 1-yo'ldan k-yo'lgacha bo'lgan eng qisqa yo'ldan olingan ketma-ketlikning eng uzun o'sib boruvchi pastki ketma-ketligi uzunligini chop eting.