المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۲۱:سوال ۲

Tree

به شما درخت $T$ داده شده است. فرض كنید فاصله دو به دوی رئوس متفاوت این درخت را در آرایه $A$ ریخته‌ایم و آن‌ها را مرتب کرده‌ایم. در این صورت $A[1]$ برابر است با فاصله دو راسی که کم‌ترین فاصله را دارد و $A[n(n-1)/2]$ برابر بزرگ‌ترین مسیر درخت است.

شما باید با گرفتن عدد $k$ از ورودی $A[k]$ را چاپ كنید.

ورودی

  • در سطر اول ورودی عدد $n \leq 200000$ نشان‌دهنده تعداد رئوس درخت و عدد $1 \leq k \leq n(n-1)/2$ آمده است.
  • در هر یک از $n-1$ سطر بعدی یک یال درخت به صورت دو عدد $1 \leq u_i, v_i \leq n$ می‌آید.

خروجی

در تنها سطر خروجی پاسخ سوال را چاپ نمایید.

محدودیت‌ها

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

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
3 2
1 2
2 3
1
3 3
1 2
2 3
2

ابزار صفحه