- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
پگاه که حسابی غرقِ ریاست شده‌است تصمیم گرفته از بین غول‌پیکرها برای خود چندتا مأمور مخصوص انتخاب کند و نشانِ مأمورِ مخصوصِ حاکمِ بزرگ را به آن‌ها اهدا کند.
از این رو سراغ شجره‌نامه‌ی افراد قبیله می‌رود. شجره‌نامه یک درخت $n$ رأسی است که از رأس شماره‌ی ۱ ریشه‌دار شده و هر رأس آن یکی از افراد قبیله است.
در این قبیله مقدار بدبختی هر غول‌پیکر با یک عدد نشان داده می‌شود.
هم‌چنین افراد این قبیله به علّت اعتقاد راسخی که به «فرزند بیشتر، زندگیِ شادتر» دارند؛ اعتبار هر فرد را برابر تعداد نوادگان آن فرد در شجره‌نامه قرار می دهند.
پگاه می‌خواهد مأموران مخصوص خود را به گونه‌ای انتخاب کند که مجموع بدبختی آن‌ها از $k$ بیشتر نباشد و هیچ مأموری از نوادگان مأمور دیگری نباشد.
مجموع اعتبار مأموران ویژه‌ی پگاه حداکثر چقدر می‌تواند باشد؟
ورودی
در خط اوّل دو عدد $n$ تعداد افراد قبیله و $k$ داده می‌شود که با یک فاصله از هم جدا شده‌اند.
سپس در $n-1$ خط بعد در هر خط دو عدد $u$ و $v$ آمده که با یک فاصله از هم جدا شده‌اند و نشان‌دهنده‌ی یک رابطه‌ی پدر و پسری بین غول‌پیکر شماره $u$ و غول‌پیکر شماره $v$ هستند.
در خط آخر ورودی $n$ عدد داده می‌شود که عدد $i$اُم میزان بدبختی غول‌پیکر $i$اُم را نشان می‌دهد. مقدار بدبختی هر فرد عددی طبیعی بین $1$ تا $10^9$ است. $$1\leq n \leq 1\ 000$$ $$1 \leq k \leq 100$$ $$1 \leq u, v \leq n$$
خروجی
در خروجی یک عدد که حداکثر مجموع اعتبار مأموران مخصوص پگاه است را چاپ کنید.
مثال
ورودی نمونه
5 5
1 2
1 3
3 4
3 5
6 2 5 1 3
خروجی نمونه
2
توضیح نمونه: اگر پگاه فقط غول‌پیکر شماره ۳ را انتخاب کند، مجموع اعتبار مأموران بیشینه و برابر ۲ خواهد بود.
ارسال پاسخ برای این سؤال