رالف خرابکار (Wreck-it Ralph)

رالف خرابکار در ماجراجویی خود یک درخت ریشه‌دار $n$ رأسی پیدا کرده‌ که ریشه آن راس ۱ است. روی هر رأس این درخت یک عدد طبیعی نوشته شده‌است. رالف متوجه شد که این درخت از خاصیت جالبی برخوردار است. عدد نوشته شده روی هر رأس درخت از عدد نوشته شده روی پدرش بیشتر نیست. اما متاسفانه با کمی بازی‌بازی، رالف روی درخت خرابکاری کرد و اعداد درخت بهم ریخت. حالا رالف می‌خواهد این خاصیت را به درخت برگرداند. او درخت را پیش فلیکس برده و از او درخواست می‌کند تا درخت را برایش تعمیر کند.

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

فلیکس که از خرابکاری‌های رالف خسته شده، می‌خواهد بداند که آیا میتواند درخت رالف را درست کند یا نه. همچنین اگر درخت رالف قابل درست کردن بود، باید به او بگویید حداقل چند ضربه چکش نیاز است تا درخت را درست کند و قبل از خرابکاری بعدی رالف به تعطیلات تابستانی برود.

در خط اول ورودی عدد $n$ که برابر تعداد رأس‌های درخت است می‌آید.

در خط بعد اعداد $p_2, p_3, \dots, p_n$ می‌آیند. رأس $p_i$-ام درخت، به رأس $i$-ام با یک یال متصل است.

در خط بعد اعداد $a_1, a_2, \dots, a_n$ که اعداد ابتدایی نوشته شده روی رأس‌ها هستند می‌آیند.

در تنها خط خروجی، اگر درخت قابل درست شدن بود کمینه تعداد ضربه مورد نیاز برای درست شدن درخت و در غیر این صورت $-1$ را چاپ کنید.

• زیرمسئله اول (۲ نمره): برای هر $2 \leq i \leq n$, $p_i = i-1$.
• زیرمسئله دوم (۲۰ نمره): هر رأس درخت حداکثر دو فرزند دارد.
• زیرمسئله سوم (۲۰ نمره): $n \leq 1000$ و برای هر $1 \leq i \leq n$، $1 \leq a_i \leq 1000$.
• زیرمسئله چهارم (۵۸ نمره): بدون محدودیت اضافی.

• $2 \leq n \leq 10^5$
• $1 \leq p_i < i$
• $1 \leq a_i \leq 10^9$