• محدودیت زمان: ۲ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت
  • منبع: آزمون عملی دوره ۲۴ المپیاد کامپیوتر

شرکت عمرانی «بساز و بنداز» در آستانه ورشکست شدن است و آقای مهندس، مدیر شرکت قصد تعدیل نیرو دارد. منطقی است که او نیز مانند مدیر‌های با لیاقت دیگر نمی‌‌خواهد کارمندان خوبش را از دست بدهد، برای همین آزمایشی برای سنجش خلاقیت کارمندانش ترتیب داده است. طی این آزمایش او به هر کدام از کارمندان، نقشه پروژه جدید شرکت را که عملیات راه‌سازی یک شهرک صنعتی است، داده است.

در این شهرک nn ساختمان وجود دارد که با n1n - 1 جاده به هم متصل شده‌اند، به طوری که از هر ساختمانی می‌توان به هر ساختمان دیگری رسید. (یعنی گراف بین ساختمان‌ها یک درخت است) قرار است طول هر کدام از این n1n - 1 جاده طوری تعیین شود که طول جاده iiام عدد صحیحی در بازه [li,ri][l_i, r_i] باشد، هم‌چنین ساختمان‌ها نباید خیلی از هم دور باشند. از نظر آقای مهندس وقتی ساختمان‌ها خیلی از هم دور نیستند که جمع فاصله دوبه‌دوی ساختمان‌ها حداکثر kk باشد. (جمع n×(n1)/2n \times (n - 1) / 2 فاصله)

آقای مهندس به کارمندان گفته‌است که اگر دو نفر از آن‌ها وزن همه‌ی یال‌هایشان را یکسان تعیین کنند، حتماً یکی از آن‌ها اخراج می‌شود. اما چیزی که ذهنش را مشغول کرده این‌ است که شرکت بعد از تعدیل نیرو حداکثر چند کارمند دارد و از شما خواسته است این مقدار را به دست آورید.

ورودی

در خط اول ورودی دو عدد nn و kk آمده‌اند که nn تعداد ساختمان‌های شهرک و kk حداکثر جمع فاصله دوبه‌دوی ساختمان‌ها را نشان می‌دهد. در n1n - 1 خط بعد، در هر خط اطلاعات یکی از جاده‌های بین ساختمان‌ها آمده است. هر خط شامل چهار عدد uiu_i و viv_i و lil_i و rir_i است که وجود یک جاده دوطرفه از ساختمان uiu_i به ساختمان viv_i را نشان ‌می‌دهند، که طولش باید حداقل lil_i و حداکثر rir_i باشد.

1n,k100 0001 \le n, k \le 100\ 000

1ui,vin1 \le u_i, v_i \le n

1liri100 0001 \le l_i \le r_i \le 100\ 000

خروجی

در تنها خط خروجی باقی‌مانده حداکثر تعداد کارمندان بعد از تعدیل نیرو را بر 109+710^9+7 چاپ کنید.

زیرمسئله‌ها

زیرمسئله نمره محدودیت
۱ ۳۵ 1n100 1 \le n \le100 , 0rili10 0 \le r_i - l_i\le 10
۲ ۱۰ یک ساختمان به طور مستقیم به همه جاده ها وصل است
۳ ۵۵ بدون محدودیت اضافی

مثال

ورودی نمونه ۱

5 22
1 2 1 2
2 3 1 2
3 4 1 2
3 5 1 2
Plain text

خروجی نمونه ۱

4
Plain text

(۲۴امین دوره المپیاد کامپیوتر - آزمون یکم - ۱۳۹۳/۰۵/۲۳)


ارسال پاسخ برای این سؤال
فایلی انتخاب نشده است.