ثانیه‌‌های آخر


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

توضیح تصویر

در پایان شهریور خونین بالاخره تکلیف کاراکتر اصلی ۱ روشن شد و او چشم از جهان بست تا دیگر کسی نتواند کاراکترهای کمکی بی گناه را اذیت کند. اما از آنجایی که داستان این کانتست بسیار غم انگیز می‌شود اگر کاراکتر اصلی ۱ تنها و بی‌کس و در میان انبوهی از کاراکترهای کمکی بمیرد، پس یک کاراکتر اصلی ۰ای پیدا می‌شود که از قضا در زمانی که کاراکتر اصلی ۱ خودش هم کاراکتر کمکی بوده، معلمش بوده است. در این لحظات آخر زندگی برای کاراکتر اصلی ۱، کاراکتر اصلی ۰ سر او را روی پاهایش می‌گذارد و می‌خواهد کاری کند که او در هنگام مرگش با رضایت و شادکامی از دنیا برود، به همین دلیل در qq ثانیه‌ی آخر زندگی کاراکتر اصلی ۱، qq سوال از او می‌پرسد:

سوال او بی‌ربط به فضای اطراف آن‌ها در این لحظات نیست، درختی در حیاط مدرسه وجود دارد که رئوسش شماره‌گذاری شده‌اند و ریشه‌دار است و ریشه‌ی آن راس ۱ است. کاراکتر اصلی ۰ در هر ثانیه شماره‌ی دوتا از رئوس این درخت را به کاراکتر اصلی ۱ می‌دهد و چون در لحظات مرگ کمی از بنیه‌ی علمی و توان کاراکتر اصلی ۱ کم شده است تضمین می‌کند که راس دومی که داده است حتما در زیردرخت راس اول است. به عبارت دیگر v v و uu را می‌دهد که u u در زیردرخت vv است. چیزی که کاراکتر اصلی ۱ باید بگوید این است که طول بزرگترین مسیر در زیردرخت vv با شروع از uu چقدر است به عبارت دیگر اگر بقیه‌ی درخت به غیر از زیردرخت راس vv حذف شود، بلندترین مسیری که یک راس آن uu باشد چه طولی دارد.

کاراکتر اصلی ۱ دانا که تمام این اتفاقات را از قبل پیش بینی می‌کرده است دستگاهی ساخته و با خود همراه دارد که جواب تمام این سوالات کاراکتر اصلی ۰ را بدهد تا او فکر کند که کاراکتر اصلی ۱ با شادی از دنیا رفته است.

برنامه‌ای بنویسید که مانند دستگاه کاراکتر اصلی ۱ عمل کند و به سوالات کاراکتر اصلی ۰ پاسخ دهد.

ورودی🔗

در خط اول ورودی دو عدد طبیعی nn و qq داده می‌شوند.

در خط بعدی n1n - 1 عدد که iiامین عدد نشان‌دهنده‌ی شماره‌ی راس پدر راس i+1i + 1 است.

در qq خط بعدی qq پرسش مطرح می‌شوند، در هر خط دو عدد vv و uu را می‌دهد.

1n100 0001 \leq n \leq 100 \ 000 1q100 0001 \leq q \leq 100 \ 000 1v,un1 \leq v, u \leq n

خروجی🔗

در qq خط پاسخ qq پرسش مطرح شده را بدهید.

مثال🔗

ورودی نمونه🔗

7 3
1 1 2 2 3 3
1 5
2 5
7 7
Plain text

خروجی نمونه🔗

4
2
0
Plain text

توضیح🔗

در ثانیه‌ی اول، کاراکتر اصلی ۱ باید بلندترین مسیر با شروع از راس ۵ در کل درخت رو بگوید (زیردرخت ریشه، کل درخت را شامل می‌شود) که بلندترین مسیر با شروع از راس ۵، مسیر ۵ ۲ ۱ ۳ ۶ یا ۵ ۲ ۱ ۳ ۷ می باشند که طولشان ۴ است.

در ثانیه‌ی دوم، کاراکتر اصلی ۱ باید بلندترین مسیر با شروع از راس ۵ در زیردرخت راس ۲ (شامل رئوس ۲، ۴ و ۵) را بگوید، که مسیر ۵ ۲ ۴ و به طول ۲ است.

در ثانیه‌ی سوم، کاراکتر اصلی ۱ باید بلندترین مسیر با شروع از راس ۷ در زیردرخت خود راس ۷ را بگوید. چون راس ۷ برگ است و زیردرخت راس ۷ فقط شامل خودش است، پس طول بلندترین مسیر در آن ۰ است.

شکل سوال