خانواده بلک یکی از اصیل ترین خانوادهها میان خانوادههای جادوگری است و همه اعضای آن به…
- User
خانواده بلک یکی از اصیل ترین خانوادهها میان خانوادههای جادوگری است و همه اعضای آن به شجرهنامه خانواده خود بسیار اهمیت میدهند. شجرهنامه این خانواده به شکل یک درخت است و ریشه آن بزرگترین فرد خانواده بلک است. در این خانواده سنتهای زیادی وجود دارد. مثلن گاهی یکی از اعضای خانواده تصمیم میگیرد جایزهای برای بچههایش بگیرد. نحوه جایزه دادن به این صورت است که فرد جایزهدهنده در آن روز جایزه را پیش خودش نگهمیدارد و فردایش آن جایزه را به یکی از فرزندانش (در صورت وجود) میدهد. در صورتی که آن شخص، فرزندی نداشته باشد جایزه پیش خودش میماند. وگرنه فرزندش همین کار را تکرار میکند. یعنی جایزه را یک روز پیش خود نگه میدارد و فردایش آن را به یکی از فرزندانش میدهد. این کار آنقدر تکرار میشود تا جایزه به یکی از بلکهای جوان برسد. (منظور عضوی از خانوادهاست که هنوز فرزندی ندارد یعنی یکی از برگهای درخت شجرهنامه)
با گرفتن زمان جایزه فرستادنها و شخصفرستنده جایزه به سوالاتی شبیه سوال زیر پاسخ دهید:
یک عضو جوان خانواده بلک تا یک روز مشخص حداکثر چند جایزه گرفته است؟ ورودی در خط اول ورودی دو عدد n و q آمده اند که n تعداد اعضای خانواده بلک و q تعداد استفسارات (queryها) را نشان میدهد. در خط بعد n-1 عدد p 2 . . . p n p 2 ...p n آمده است که شجره نامه خانواده بلک را مشخص میکند. فرض کنید اعضای خانواده به ترتیب سن با اعداد 1 تا n شمارهگذاری شدهاند. عدد p i p i شماره پدر(یا مادر) عضو شماره i را نشان میدهد. رأس شماره 1 اولین عضو خانواده بلک است.
در هر یک از q خط بعد در هر خط یک استفسار آمده است. در اول هر خط یک کاراکتر آمده است که نوع استفسار را مشخص میکند. کاراکتر $ نشان دهنده جایزه دادن و ? نشان دهنده پرسش است.
در حالت $، در ادامه دو عدد v و t آمده است که نشان میدهد عضو شماره vام خانواده در روز t تصمیم میگیرد جایزه بخرد! دقت کنید که یک نفر ممکن است جوان باشد و برای خودش جایزه بگیرد.
در حالت ?، در ادامه دو عدد v و t آمده است که نشان میدهد عضو شماره vآم خانواده از ابتدا تا روز t (شامل خود این روز) حداکثر چند جایزه گرفته است؟ تضمین میشود که این عضو یک بلک جوان است(فرزندی ندارد).
استفسارات به ترتیب نانزولی برحسب زمان در ورودی ظاهر شدهاند.
2 ≤ n ≤ 200
000 2≤n≤200 000 1 ≤ p i ≤ i − 1 , 2 ≤ i ≤ n 1≤p i ≤i−1,2≤i≤n
1 ≤ q ≤ 200
000 1≤q≤200 000
1 ≤ v ≤ n 1≤v≤n
1 ≤ t ≤ 1 0 9 1≤t≤10 9
خروجی در خروجی به ازای هر پرسش، جواب آن را در یک خط چاپ کنید.
زیرمسئلهها زیرمسئله نمره محدودیت ۱ ۱۵ n , q ≤ 2
000 n,q≤2 000 ۲ ۱۰ n , q ≤ 50
000 n,q≤50 000 و هر خانواده حداکثر یک بچه دارد. (گراف شجرهنامه یک مسیر است.) ۳ ۵۵ n , q ≤ 50
000 n,q≤50 000 ۴ ۲۰ بدون محدودیت اضافی مثال ورودی نمونه 5 8 1 2 2 1 1 4 $ 2 4 ? 3 4 ? 3 5 ? 3 6 ? 5 6 Plain text خروجی نمونه 1 1 2 3 1
- Assistant
برای حل این مسئله، باید نحوهی انتقال جوایز در درخت خانواده را بهصورت مؤثر مدیریت کنیم و بتوانیم پاسخ به سوالات به سرعت و با دقت بدهیم. در این مسئله، ما با دو نوع عملیات مواجه هستیم:
-
عملیات
$ v t: این عملیات بیان میکند که عضوvدر روزtتصمیم به خرید یک جایزه میگیرد. جایزه ابتدا در خود عضو نگه داشته میشود و سپس یک روز بعد به یکی از فرزندانش منتقل میشود و این روند تا رسیدن جوایز به یکی از برگهای درخت ادامه مییابد. -
عملیات
? v t: این سوال از ما میخواهد که تا روزt، حداکثر چند جایزه به عضو جوانvرسیده است.
برای پاسخ به این سوالات با کارایی بالا، از تکنیکهای مختلفی از جمله Heavy-Light Decomposition (HLD) و Binary Indexed Tree (BIT) استفاده میکنیم. مراحل زیر شرح داده شده است:
-
ساخت درخت: ابتدا درخت خانواده را بر اساس ورودیها میسازیم و عمق هر عضو از ریشه محاسبه میکنیم.
-
تکنیک HLD: با استفاده از HLD، درخت را به بخشهای بزرگ و سبک تقسیم میکنیم تا بتوانیم مسیرها را به صورت مؤثری مدیریت کنیم.
-
دستکاری رویدادها: همه عملیاتهای
$و?را خوانده و آنها را بر اساس زمان مرتب میکنیم. این کار به ما اجازه میدهد تا رویدادها را به ترتیب زمانی پردازش کنیم و اطلاعات مورد نیاز برای پاسخ به سوالات را ذخیره کنیم. -
استفاده از BIT: با استفاده از BIT، به ما اجازه داده میشود تا در هر مرحله تعداد جوایز دریافتی توسط اعضا را بهروزرسانی و پرسوجو کنیم.
-
پاسخ به سوالات: پس از پردازش تمام رویدادها، پاسخ به هر سوال را بر اساس تعداد جوایزی که تا آن زمان به عضو مربوطه رسیده است، محاسبه میکنیم.
به عنوان مثال، برای ورودی نمونه داده شده، خروجی به شکل زیر است:
1 1 2 3 1این خروجی نشان میدهد که عضو جوان مورد نظر در روزهای مختلف تا آن زمان حداکثر چند جایزه دریافت کرده است.
پاسخ نهایی:
1 1 2 3 1 -