+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت + آزمون عملی دوم فاینال سی و دومین دوره المپیاد کامپیوتر ایران ---------- ‌ا Scarecrow به گاتهام آمده و مردم شهر را مسموم کرده است. Batman با کمک دستیارانش توانسته پادزهری بسازد که مردم را شفا بدهد و حالا می‌خواهد آن را بین مردم پخش کند. نقشه شهر گاتهام به صورت یک درخت $n$ راسی می‌باشد که هر راس از آن یک منطقه را نشان می‌دهد. بتمن یک منطقه مانند $v$ را انتخاب می‌کند و پادزهر را از آن منطقه منتشر می‌کند. بتمن با افسر گوردن هماهنگ کرده است تا دقیقا یکی از جاده‌ها (یال) را غیر قابل عبور کند تا اهالی منطقه $v$ نتوانند از فاصله $k$ این منطقه دورتر بروند زیرا اگر بتوانند خود را به منطقه‌ای برسانند که فاصله آن با $v$ حداقل $k$ جاده باشد، پادزهر روی آن‌ها اثر نمی‌کند. به همین خاطر افسر گوردن از بتمن می‌خواهد تا تعداد جاده‌هایی که با بسته شدن آن‌ها پادزهر اثر **نمی‌کند** را به او بگوید. بتمن که هنوز راس اولیه و مقدار $k$ را انتخاب نکرده است، از شما کمک می‌خواهد تا این تعداد را به ازای $Q$ سناریو مختلف جواب دهید. # ورودی در خط اول دو عدد طبیعی $n$ تعداد مناطق گاتهام و $q$ تعداد سناریوها به‌ترتیب می‌آیند. در خط بعدی دنباله $p_2, p_3, \cdots, p_{n}\ $ می‌آیند. به ازای هر $2 \leq i \leq n$ جاده‌ای میان دو منطقه $i$ و $p_i$ وجود دارد. در هر یک از $q$ خط بعدی، دو عدد طبیعی $v_i$ و $k_i$ می‌آیند. # خروجی در $q$ خط جواب مربوط به هر سناریو را چاپ کنید. # محدودیت‌ها $$1 \leq n, q \leq 300 \, 000$$ $$1 \leq p_i \leq i - 1$$ $$1 \leq v_i, k_i \leq n$$ # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت |:------------------:|:----------:|:------------------:| | ۱ | ۸ | $p_i = i-1$ به ازای تمامی $2 \leq i \leq n$ برقرار است. | | ۲ | ۱۳ | $n \leq 300$ و $q \leq 1000$ | | ۳ | ۲۲ | $n, q\leq 1000$ | | ۴ | ۱۸ | $n, q \leq 100 \, 000$ و فاصله منطقه $1$ با دورترین منطقه از آن حداکثر $40$ جاده می‌باشد. | | ۵ | ۲۸ | $n, q \leq 100 \, 000$ | | ۶ | ۱۱ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 5 5 1 1 3 4 1 2 4 1 2 1 2 2 3 3 ``` ## خروجی نمونه ۱ ``` 2 4 3 2 0 ``` ## ورودی نمونه ۲ ``` 10 1 1 2 3 4 5 4 7 6 9 8 5 ``` ## خروجی نمونه ۲ ``` 7 ``` گراف ورودی دوم به شکل زیر است. |  | |:--------:| | شکل ۱: شکل گراف نمونه ورودی ۲ | اگر افسر گوردن هر جاده‌ای به جز جاده‌های بین $\langle 4, 7 \rangle$ یا $\langle 7, 8 \rangle$ را ببندد، مردم می‌توانند از منطقه $8$ به حداقل یکی از مناطق $1$ یا $9$ بروند و پادزهر روی آن‌ها اثر نگذارد.

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