+ محدودیت زمان: ۲.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- اخیرا اساتید مدرسه‌ی جادوگری هاگوارتز نام «امیرمحمّد ایمانی» زیاد به گوششان خورده و به دامبلدور، مدیر مدرسه، پیشنهاد می‌دهند که برای امیرمحمّد دعوت‌نامه‌ای بفرستد تا امیرمحمّد بتواند در این مدرسه ادامه تحصیل دهد. دامبلدور دستی به محاسنش می‌کشد و می‌گوید: «باشه بهش می‌گم...». سپس با یک سوت بلبلی جغدش را صدا می‌زند و دعوت‌نامه‌ی امیرمحمّد را با جغدش برای او می‌فرستد. امیرمحمّد ابتدا از دیدن جغد شوکه می‌شود و شروع به جیغ کشیدن و فرار کردن می‌کند. جغد اعصابش خرد می‌شود و فریاد می‌زند: «بسه باو کر شدیم. بیا دعوت‌نامه‌تو بگیر این جا رم امضا کن ما بریم پی کارمون. :/» امیرمحمّد دعوت‌نامه را امضا می‌کند و مشغول تحصیل می‌شود. پس از چندین ماه تحصیل و تمرین و ممارست، حسابی در جادوگری پیشرفت می‌کند و به درجات بالای علمی می‌رسد. یک روز که او داشت برای خودش در جنگل کنار مدرسه قدم می‌زد، آقا گرگه جلوی او را می‌گیرد و می‌گوید: «بیا بخورمت.». امیرمحمّد می‌گوید: «بیی‌خیال... بذار برم غذا بخورم چاااق بشم... چلّه بشم... بعد می‌آم تو منو بخور.» خلاصه از آقا گرگه اصرار و از امیرمحمّد انکار...  تا این که آقا گرگه خسته می‌شود و $n$ درخت $n$ راسی که **دقیقا مشابه** یکدیگر هستند را به امیرمحمّد نشان می‌دهد و می‌گوید: «اصلا مگه تو جادوگر نیستی؟ بیا این $n$ تا درخت رو برام غیب کن!» امیرمحمّد بادی در غبغب می‌اندازد و می‌گوید: «بله که هستم! بذار الآن غیبشون می‌کنم!». او می‌خواهد درخت‌ها را به ترتیب غیب کند. یعنی اوّل درخت اوّل، سپس درخت دوم و... طلسمی که امیرمحمّد برای این کار بلد است، ابتدا دارای قدرت $n$ است. امّا هر بار که امیر محمّد یک درخت را به طور کامل غیب می‌کند، یک واحد از قدرتش کاسته می‌شود. یعنی پس از غیب کردن تمام درخت‌ها قدرت طلسم به $0$ می‌رسد. این طلسم به این شکل عمل می‌کند که هر بار امیرمحمّد یکی از رئوس درخت(مثل $v$) را نشانه می‌گیرد و با اعمال آن طلسم، تمام رئوس در زیردرخت $v$ که فاصله‌شان از $v$ حداکثر به اندازه‌ی قدرت آن طلسم است، غیب می‌شوند. (راس $v$ می‌تواند از قبل غیب شده باشد) برای امیرمحمّد برنامه‌ای بنویسید که بگوید برای غیب کردن تمامی این $n$ درخت $n$ راسی چند بار باید از طلسمش استفاده کند. نکته: این درخت‌ها ریشه‌دار هستند. یعنی راس $u$ در زیردرخت راس $v$ قرار دارد اگر و فقط اگر در مسیر ریشه به $u$، راس $v$ ظاهر شود. هم‌چنین ریشه‌ی تمام این درخت‌ها راس $1$ است. # ورودی در سطر اول ورودی عدد $n$ آمده‌است.\ در هر یک از $n - 1$ سطر بعد دو عدد آمده است که نشان‌دهنده‌ی اعداد دو سر هر یال هستند. تضمین می‌شود یال‌هایی که در ورودی داده می‌شود تشکیل یک درخت می‌دهند. + $1 \le n \le 10^{5}$ + $1\le $ اعداد دو سر یال $\le n$ # خروجی در تنها سطر خروجی، عددی که امیرمحمّد می‌خواهد را چاپ کنید. # زیر مسئله ها | زیرمسئله | نمره | محدودیت ها | |:-----------:|:------------------:|:------------------:| | ۱ | ۴ | $n \le 100$ | | ۲ | ۱۷ | $n \le 5000$ | | ۳ | ۷۹ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 4 1 2 2 3 2 4 ``` ## خروجی نمونه ۱ ``` 5 ``` ## ورودی نمونه ۲ ``` 6 1 2 1 3 1 4 4 5 4 6 ``` ## خروجی نمونه ۲ ``` 7 ```

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