کاهش


  • محدودیت زمان: ۰.۵ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

کروکی درون باغ لیکوئید یک درخت سیب دارد. این درخت از پایین به بالا به شکل یک درخت ریشه دار است. راس‎های درخت از 00 تا n1n-1 نام گذاری شده‎اند و ریشه این درخت راس 00 است. کروکی می داند که درخت‎های سیب تنها در برگ‎ها میوه می‎دهند. جی‎اچ به او گفته است که اگر راس ii برگ باشد در سال aia_i تا سیب می دهد. کروکی می‎خواهد با قیچی باغبانی خود شاخه‎هایی از درخت را ببرد به صورتی که درخت باقیمانده دقیقا kk برگ داشته باشد، شامل راس ریشه باشد و تعداد سیب‎‏هایی که در سال می دهد بیشینه باشد. به کروکی کمک کنید که این مقدار بیشینه را بدست آورد.

ﺗﻮجه ﮐﻨﯿﺪ ﮐﻪ راس رﯾﺸﻪ ﺗﻨﻬﺎ در ﺻﻮرتی ﺑﺮگ ﺣﺴﺎب می‎ﺷﻮد ﮐﻪ ﺗﻨﻬﺎ راس ﺑﺎﻗﯿﻤﺎﻧﺪه در درﺧﺖ ﺑﺎﺷﺪ.

ورودی🔗

در ﺳﻄﺮ اول ﺑﻪ ﺗﺮﺗﯿﺐ اﻋﺪاد nn و kk آمده‎اند

در ﺳﻄﺮ دوم nn عدد a0,a1,a2,...,an1a_0,a_1,a_2,...,a_{n-1} آمده‎است.

در ii امین سطر از n1n-1 سطر بعد دو عدد viv_i و uiu_i آمده‎اند که نشان دهنده وجود یک شاخه بین راس viv_i و uiu_i در درخت است.

1n100 000 1 \le n \le 100\ 0001k100 1 \le k \le 1001ai1 000 000 000 1 \le a_i \le 1\ 000\ 000\ 0000vi,ui<n 0 \le v_i,u_i \lt n

تضمین می‎شود شاخه‎های ورودی تشکیل یک درخت می‎دهند.

تضمین می شود درخت در ابتدا حداقل kk برگ دارد.

خروجی🔗

در ﺗﻨﻬﺎ ﺳﻄﺮ ﺧﺮوجی، ﺑﯿﺸﺘﺮﯾﻦ ﺗﻌﺪاد ﺳﯿﺒﯽ ﮐﻪ درﺳﺎل می‎ﺗﻮان ﺗﻮﻟﯿﺪ ﮐﺮد را ﭼﺎپ ﮐﻨﯿﺪ.

زیرمسئله‌ها🔗

زیرمسئله نمره محدودیت
۱ ۱۱ n20n \le 20
۲ ۱۸ k2k \le 2
۳ ۲۲ n500n \le 500
۴ ۴۹ بدون محدودیت اضافی

مثال🔗

ورودی نمونه ۱🔗

8 3 
83 91 9 12 15 11 7 8
0 1
0 2
1 3
1 4
3 5
4 6
4 7
Plain text

خروجی نمونه ۱🔗

36
Plain text

ورودی نمونه ۲🔗

3 1
1 2 3
0 1
0 2
Plain text

خروجی نمونه ۲🔗

3
Plain text

ورودی نمونه ۳🔗

3 1
3 2 1
0 1
0 2
Plain text

خروجی نمونه ۳🔗

3
Plain text