سوال ۱

خانواده بلک یکی از اصیل‌ترین خانواده‌ها میان خانواده‌های جادوگری است و همه اعضای آن به شجره‌نامه خانواده خود بسیار اهمیت می‌دهند. شجره‌نامه این خانواده به شکل یک درخت است و ریشه آن بزرگترین فرد خانواده بلک است.

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

با گرفتن زمان جایزه فرستادن‌ها و شخص فرستنده جایزه به سوالاتی شبیه سوال زیر پاسخ دهید:

یک عضو جوان خانواده بلک تا یک روز مشخص حداکثر چند جایزه گرفته است؟

• در خط اول ورودی دو عدد $n$ و $q$ آمده‌اند که $n$ تعداد اعضای خانواده بلک و $q$ تعداد استفسارات (queryها) را نشان می‌دهد. در خط بعد $n − 1$ عدد $p_2$ تا $p_n$ آمده است که شجره‌نامه خانواده بلک را مشخص می‌کند. فرض کنید اعضای خانواده به ترتیب سن با اعداد $1$ تا $n$ شماره‌گذاری شده‌اند. عدد $p_i$ شماره پدر (یا مادر)‌ عضو شماره $i$ را نشان می‌دهد. راس شماره $1$ اولین عضو خانواده بلک است.
• در هر یک از $q$ خط بعد در هر خط یک استفسار آمده است. در اول هر خط یک کاراکتر آمده‌است که نوع استفسار را مشخص می‌کند. کاراکتر \$ نشان‌دهنده جایزه دادن و ? نشان‌دهنده پرسش است.
• در حالت \$، در ادامه دو عدد $v$ و $t$ آمده است که نشان می‌دهد عضو شماره $v$ام خانواده در روز $t$ تصمیم می‌گیرد جایزه بخرد! دقت کنید که یک نفر ممکن است جوان باشد و برای خودش جایزه بگیرد.
• در حالت ?، در ادامه دو عدد $v$ و $t$ آمده است که نشان‌دهنده این پرسش است: عضو شماره $v$ خانواده از ابتدا تا روز $t$ (شامل خود این روز) حداکثر چند جایزه گرفته است؟ تضمین می‌شود که این عضو یک بلک جوان است. (فرزندی ندارد)
• استفسارات به ترتیب نانزولی بر حسب زمان در ورودی ظاهر شده‌اند.
• $2 \leq n \leq 2 * 10^5$
• $1 \leq p_i \leq i − 1 (2 \leq i \leq n)$
• $1 \leq q \leq 2 * 10^5$
• $1 \leq v \leq n$
• $1 \leq t \leq 10^9$

در خروجی به ازای هر پرسش، جواب آن را در یک خط چاپ کنید.

• زیرمسئله اول (۱۵ نمره): $n, q \leq 2000$
• زیرمسئله دوم (۱۰ نمره): $n, q \leq 50000$ و هر کس در خانواده حداکثر یک بچه دارد. (گراف شجره‌نامه یک مسیر است)
• زیرمسئله سوم (۵۵ نمره): $n, q \leq 50000$
• زیرمسئله چهارم (۲۰ نمره): بدون محدودیت اضافی

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

• سوال بعد