+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- کروکی درون باغ لیکوئید یک درخت سیب دارد. این درخت از پایین به بالا به شکل یک درخت ریشه دار است. راس‎های درخت از $0$ تا $n-1$ نام گذاری شده‎اند و ریشه این درخت راس $0$ است. کروکی می داند که درخت‎های سیب تنها در برگ‎ها میوه می‎دهند. جی‎اچ به او گفته است که اگر راس $i$ برگ باشد در سال $a_i$ تا سیب می دهد. کروکی می‎خواهد با قیچی باغبانی خود شاخه‎هایی از درخت را ببرد به صورتی که درخت باقیمانده دقیقا $k$ برگ داشته باشد، شامل راس ریشه باشد و تعداد سیب‎‏هایی که در سال می دهد بیشینه باشد. به کروکی کمک کنید که این مقدار بیشینه را بدست آورد. ﺗﻮجه ﮐﻨﯿﺪ ﮐﻪ راس رﯾﺸﻪ ﺗﻨﻬﺎ در ﺻﻮرتی ﺑﺮگ ﺣﺴﺎب می‎ﺷﻮد ﮐﻪ ﺗﻨﻬﺎ راس ﺑﺎﻗﯿﻤﺎﻧﺪه در درﺧﺖ ﺑﺎﺷﺪ. # ورودی در ﺳﻄﺮ اول ﺑﻪ ﺗﺮﺗﯿﺐ اﻋﺪاد $n$ و $k$ آمده‎اند در ﺳﻄﺮ دوم $n$ عدد $a_0,a_1,a_2,...,a_{n-1}$ آمده‎است. در $i$ امین سطر از $n-1$ سطر بعد دو عدد $v_i$ و $u_i$ آمده‎اند که نشان دهنده وجود یک شاخه بین راس $v_i$ و $u_i$ در درخت است. $$ 1 \le n \le 100\ 000$$$$ 1 \le k \le 100$$$$ 1 \le a_i \le 1\ 000\ 000\ 000$$$$ 0 \le v_i,u_i \lt n$$ تضمین می‎شود شاخه‎های ورودی تشکیل یک درخت می‎دهند. تضمین می شود درخت در ابتدا حداقل $k$ برگ دارد. # خروجی در ﺗﻨﻬﺎ ﺳﻄﺮ ﺧﺮوجی، ﺑﯿﺸﺘﺮﯾﻦ ﺗﻌﺪاد ﺳﯿﺒﯽ ﮐﻪ درﺳﺎل می‎ﺗﻮان ﺗﻮﻟﯿﺪ ﮐﺮد را ﭼﺎپ ﮐﻨﯿﺪ. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت | |:-------:|:----------:|:-----------:| |۱ | ۱۱ | $n \le 20 $| |۲| ۱۸ | $k \le 2 $ | |۳| ۲۲ |$n \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 ``` ## خروجی نمونه ۱ ``` 36 ``` ## ورودی نمونه ۲ ``` 3 1 1 2 3 0 1 0 2 ``` ## خروجی نمونه ۲ ``` 3 ``` ## ورودی نمونه ۳ ``` 3 1 3 2 1 0 1 0 2 ``` ## خروجی نمونه ۳ ``` 3 ```