برداشت محصول از سیب

اخیراً عبدُل از مزرعه قبلی اش در عبدُل آباد (:د) به علت اذیت های توس زورگو (:د ) داروغه شهر مهاجرت کرده و یک مزرعه در روستای کاهو خریده است این روستا با وجود از بین رفتن زمان خان ها اما هنوز نیز خان داشت حاکمی ظالم به نام آرش خان ! مزرعه او بسیار بزرگ است و تنها اشکال آن این است که فقط یک درخت دارد آن هم درخت سیب ! بقیه مزرعه نیز کاهو و کلم برگ کاشته شده است .

درخت سیب او بسیار بزرگ و تنومند بود و میوه های خوش مزه داشت اما تنها بدی آن این بود که میوه هایش کوچک بودند . برای همین با دوستش محمد مهدی (که یکی از خفن های روستایش بود) پیش بهترین دکر منطقه یعنی دکتر کاملی با وجود آن که طوفان شدیدی می آمد رفتند و از ایشان که در زمینه ترکیبیات مهارت خاصی داشتند خواستن آنها را در بهبود میوه های این درخت یاری کنند پس از سیر تا پیاز مشخصات درخت را پیش دکتر گفتند . دکتر گفتند : این درخت نیاز به حرس کردن دارد ایشان ادامه دادند باید دقیقا $n$ شاخه را ببرید ! عبدًل در جواب گفت چه کسی آخه ! من که بلد نیستم پویان (یکی از شاگردان دکتر) در حالی که روبیک بازی می کرد گفت:هه هه هه این که کاری نداره من میام حرس می کنم . پس اون ها با پویان راهی روستا شدند .

آن ها درخت را بررسی کردند نتایج به شرح زیر است :

درخت ریشه دار بود و تنها اطلاعاتی که از میوه درخت بود این بود که عددی در روی هر راس (محل جدایی شاخه ها) نوشته شده که مشخص کنند تعداد میوه ها در زیر درخت آن راس می باشد و اینکه هر چه شاخه ضافی و بدون میوه حذف شود به ازای هر شاخه اضافی وزن میوه ها 2 برابر می شود .

• عمل قطع کردن یک شاخه بدین معنا است که ازگر درخت را به گراف مدل کنیم بک یال و تمام یال های زیر گراف پایین اش رو حذف کنیم .

حالا عبدُل می خواد مجموع وزن میوه ها بیشتر بشه تا به هدایتی (تاجر بزرگ شهر) بفروشه و سود بیشتری بکنه ! راستی یادم رفت آقای همساده هم زحمت حمل محصول رو میکشن ! به پویان کمک کنید که بتونه خواسته عبُل رو برآورده کنه

ورودی :

ابتدا $n$ $(n\leq 1000)$ که تعداد حرس کردن (تعداد بار های قطع شاخه ) ها و $u$ $(u\leq 1000)$ (تضمین شده $u$ از $n$ بزرگ تر است ) تعداد رئوس و سپس یک آرایه $u$ تایی که $a_{i}$ یعنی پدر راس $i$ و راسی که پدرش 0 است یعنی همان ریشه و در خط بعد یک آرایه به نام $mass$ که $mass_{i}$تعداد میوه های زیر درخت راس $i$ است .

خروجی :

ماکسیمم وزن کل میوه ه باقی مانده بر $Mod$ !

$Mod = 1000000007 $

توجه : بعد ها معوم شد که عبدُل همون کنکوری خودمونه و با وجود اینکه رتبه 1 کنکور شد بعلت بیکاری به مزرعه داری پرداخته بود (اینم عاقبته کنکور خوندنه دیگه :د )

موفق باشید !

دوستان از متن اصلی سوال غافل نشید سوال خوبیه به نظرم :د