Сімейний статок#3342
Під час вивчення історії заможних родин дослідники прагнуть визначити, наскільки велике багатство кожна родина накопичила. Існують різні значення "чистої вартості" для кожної особи в історії, але підсумовування ускладнюється через подвійний підрахунок, викликаний спадкуванням. Один зі способів оцінити багатство родини — це підсумувати чисту вартість набору з людей так, щоб ніхто в наборі не був предком або нащадком когось іншого в наборі. Багатство родини — це максимальна сума, досягнута для всіх таких наборів з людей. Оскільки історичні записи містять лише чисту вартість чоловіків-членів родини, родинне дерево є простим деревом, у якому кожен чоловік має рівно одного батька і ненегативну кількість синів. Також є рівно одна особа, яка є предком усіх інших членів родини.
Дано інформацію про родинне дерево, яким є багатство родини за цим мірилом?
Вхід міститиме кілька тестових випадків. Кожен тестовий випадок починатиметься з двох цілих чисел:
Де (1 \le N \le 100{,}000) — загальна кількість членів родини в записах, а (1 \le K \le 1{,}000) — розмір бажаного набору людей.
Кожен з наступних рядків міститиме два цілих числа:
Де (0 \le P \le N) вказує на батька цього члена родини. Члени родини пронумеровані від до , з батьком і багатством члена родини , що з'являються на -му рядку. Буде один корінь, з P=0. Дерево не матиме глибини більше ніж , і, звичайно, не матиме жодних циклів. (1 \le W \le 1{,}000) — це багатство (в мільйонах) цього члена родини.
Вхід закінчиться рядком з двома .
Для кожного тестового випадку виведіть одне ціле число в окремому рядку, яке є максимальною сумою (в мільйонах) статків набору з членів родини в дереві, де жоден член набору не є предком або нащадком будь-якого іншого члена набору. Якщо ви не можете знайти таких вузлів, тоді виведіть . Не виводьте зайвих пробілів і не розділяйте відповіді порожніми рядками.
Приклад 1