+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- فربد برای تنوع ذهنی مدتی است برنامه‌نویسی الگوریتمی را کنار گذاشته و به باغبانی روی آورده. حال فصل زمستان از راه رسیده و او می‌خواهد درخت‌های خود را هرس کند. از آنجا که تفکر الگوریتمی در تمام زندگی یار اوست او می‌خواهد هرس را طوری انجام دهد که **آویزانی ریشه کمینه می‌شود.** به عبارت دیگر [درخت‌های ریشه‌دار](https://fa.wikipedia.org/wiki/%D8%AF%D8%B1%D8%AE%D8%AA) او شبیه [درخت‌های ریشه‌دار](https://gtoi.shaazzz.ir/book/2/1.html) می‌مانند. یعنی می‌توان آنها را با گرافی $n$ راسی، همبند و بدون دور مدل کرد و **راس شماره یک** را به عنوان ریشه در نظر گرفت. میزانه آویزانی یک برگ برابر ۱ است و آویزانی رئوس دیگر برابر یک به‌علاوه بیشینه آویزانی بچه‌های آن تعریف می‌شود. همانطور که گفته‌شد او نمی‌خواهد دست به کد شود پس به او کمک کنید. **توجه کنید که او چون درخت خود را دوست دارد نمی‌خواهد بیشتر از $k$ بار آن را هرس کند و در هر عملیات هرس او دقیقا یک برگ درخت به همراه یال متصل به آن را حذف می‌کند. همچنین راسی ممکن است در ابتدا برگ نباشد و پس از تعدادی هرس به برگ تبدیل شود و نیز ریشه درخت هرس نشدنی است.** # ورودی در سطر اول ورودی $t$ به عنوان تعداد درخت‌های فربد می‌آید. سپس اطلاعات $t$ درخت به شرح زیر می‌آید. در سطر اول اطلاعات درخت $r$ عدد $n_r$ تعداد رئوس درخت و $k_r$ حداکثر تعداد هرس‌های مجاز می‌آید. سپس در سطر $i$ از $n-1$ سطر بعد در هر سطر دو عدد $u_{ri}$ و $v_{ri}$ می‌آید که نشان‌دهنده وجود یک یال بین آن دو راس است. تضمین می‌شود گراف ورودی درخت است. $$t \le 10 \, 000$$ $$1 \le n_i, \sum_{r=1}^t n_r \le 500 \, 000 \quad (1 \le i \le t)$$ $$0 \le k_r \le n_r-1 \quad (1 \le r \le t)$$ $$1 \le u_{ri}, v_{ri} \le n_r$$ # خروجی به ازای هر درخت کمینه آویزانی ریشه پس از هرس کردن حداکثر $k$ برگ را در خطوط متفاوت خروجی دهید. # مثال ## ورودی نمونه ۱ ``` 2 3 2 1 2 1 3 6 1 1 2 1 3 3 4 3 5 4 6 ``` ## خروجی نمونه ۱ ``` 1 3 ``` در درخت اول، فربد می‌تواند رأس‌های با شماره‌های ۲ و ۳ را هرس کند. پس از این کار تنها رأس باقی‌مانده رأس شماره‌ی ۱ خواهد بود که از آن‌جایی که هیچ فرزندی ندارد برگ حساب می‌شود و آویزانی آن برابر ۱ خواهد بود. در درخت دوم، فربد رأس شماره‌ی ۶ را حذف می‌کند و بدین‌ترتیب آویزانی درخت برابر ۳ خواهد شد.

حل سؤال در بانک سؤالات