کاهش


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

کروکی درون باغ لیکوئید یک درخت سیب دارد. این درخت از پایین به بالا به شکل یک درخت ریشه دار است. راس‎های درخت از 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

غول


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

مهسا در بازی فرار از خانه غول‌ها شرکت کرده‌است! روال بازی این است که شما ابتدا درون خانه قرار می‌گیرید و باید از غول‌ها فرار کنید و از خانه بیرون بیایید. اما مهسا می‌خواهد به‌جای فرار از غول‌ها، آن‌ها را به تسخیر در آورد!

در این خانه‌ nn غول وجود دارد. غول ii ، aia_i قدرت دارد و اگر مهسا بخواهد آن غول را به تسخیر در بیاورد، یا باید حداقل bib_i ( aibia_i \le b_i ) قدرت داشته باشد، یا cic_i تومن به غول پول بدهد. قدرت مهسا ابتدا صفر است. قدرت هر غولی که مهسا تسخیر کند به او اضافه می‌شود؛ یعنی اگر او غول ii را تسخیر کند، قدرت او به اندازه‌ی aia_i زیاد می‌شود.

مهسا برای خارج شدن از خانه غول‌ها، باید همه غول‌ها را تسخیر کند. او از آن‌جایی که برای ورود به بازی، هزینه‌ی بسیار زیادی پرداخته نمی‌خواهد هزینه‌ی زیادی برای تسخیر غول‌ها بپردازد؛ بنابراین از شما می‌خواهد که کمترین هزینه‌ی لازم برای تسخیر همه غول‌ها را بدست آورید.

ورودی🔗

در سطر اول ورودی عدد nn، تعداد غول‌ها آمده‌است.

سپس در ii امین سطر از nn سطر بعدی، سه عدد aia_i، bib_i و cic_i آمده‌است که به ترتیب برابر با قدرت غول ii، قدرت لازم برای تسخیر غول ii و هزینه‌ی تسخیر غول ii است.

1n2 0001 \le n \le 2\ 000 0aibi2 0000 \le a_i \le b_i \le 2\ 000 1ci2 0001 \le c_i \le 2\ 000

خروجی🔗

در تنها سطر خروجی کمترین هزینه لازم برای تسخیر کردن همه‌ی غول‌ها را چاپ کنید.

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

زیرمسئله نمره محدودیت
۱ ۱۱ n20n \le 20
۲ ۱۱ ai=bia_i = b_i
۳ ۵۱ n100n \le 100
۴ ۲۷ بدون محدودیت اضافی

مثال🔗

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

3
1 2 1
1 3 2
2 2 10
Plain text

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

3
Plain text

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

4
2 3 4
3 4 5
4 5 6
5 6 7
Plain text

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

5
Plain text

سه


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

سابیرا در کشور قزاقستان زندگی می‌کند. این کشور از nn شهر با شماره‌های 00 تا n1n-1 تشکیل شده‌است که با mm جاده دوطرفه به هم وصل شده‌اند. جاده‌ی ii-ام دو شهر uiu_i و viv_i را به هم وصل می‌کند. کریسمس نزدیک است و او می‌خواهد به قوم و خویش خود سر بزند.

او در شهر xx زندگی می‌کند؛ اقوام پدری او در شهر yy و اقوام مادری او در شهر zz زندگی می‌کنند. او می‌خواهد برای تعطیلات از شهر خود xx به شهر اقوام پدری yy و سپس به شهر اقوام مادری zz برود و در نهایت به خانه‌اش در شهر xx بازگردد.

به علت بارش سنگین برف و ناآشنا بودن سابیرا با جاده‌ها، عبور از جاده‌ی ii -ام برای بار اول aia_i دقیقه طول می‌کشد و بارهای بعد (مستقل از جهت حرکت روی جاده) bib_i دقیقه طول خواهد کشید (aibia_i \ge b_i).

سابیرا برای اینکه بیشتر در کنار اقوامش باشد می‌خواهد کمترین زمان را در جاده‌ها سپری کند. کمترین زمان سپری‌شده در جاده‌ها را پیدا کنید.

ورودی🔗

در سطر اول ورودی دو عدد nn و mm آمده‌است.

در سطر بعد به‌ترتیب سه عدد xx، yy و zz آمده‌است.

در ii امین سطر از mm سطر بعدی به‌ترتیب چهار عدد uiu_i، viv_i، aia_i و bib_i آمده‌است. 3n5003 \le n \le 500 2mn×(n1)22 \le m \le \frac{n \times (n-1)}{2} 0x,y,z<n0 \le x, y, z < n 0ui,vi<n0 \le u_i, v_i < n 0biai1090 \le b_i \le a_i \le 10^9

هیچ جاده‌ای یک شهر را به خودش وصل نمی‌کند.

بین هر دو شهر حداکثر یک جاده‌است.

سه شهر xx و yy و zz متفاوت هستند.

تضمین می‌شود که مسیری از xx به yy و از xx به zz وجود دارد.

خروجی🔗

در تنها سطر خروجی زمان کوتاه‌ترین سفر ممکن را چاپ کنید.

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

زیرمسئله نمره محدودیت
۱ ۱۴ بین هر دو شهری از nn شهر قزاقستان، دقیقا یک مسیر از جاده‌ها وجود دارد
۲ ۱۹ ai=bia_i = b_i
۳ ۶۷ بدون محدودیت اضافی

مثال🔗

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

5 6
0 1 2
0 1 20 15
0 3 7 2
3 4 4 4
4 1 10 5
4 2 15 15
2 3 14 13
Plain text

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

57
Plain text

در مثال بالا، ترتیب پیمایش بهینه شهرها {0,3,4,1,4,2,3,0}\{0, 3, 4, 1, 4, 2, 3, 0\}