Booklet Distribution
InterviewTime limit2sMemory limit1024 MB
Given a rooted tree and m booklets, choose a connected subtree containing the root that maximizes the sum of node values, where each node needs one booklet and passes the rest to children.
- Level
Medium7 of 10
- Topics
- Tree, Dynamic programming, Greedy
- Solved
- No attempts yet
Problem
The Japanese Olympiad in Informatics Committee is an organization with a very strict hierarchy. There is one chairperson, and every person other than the chairperson has exactly one supervisor. Each person in the committee has a fixed motivation value.
The committee is about to start a new project. Whether the project succeeds is believed to depend not on the number of participants but on the sum of the motivation values of the participants.
The chairperson made m booklets containing a detailed description of the project. Anyone who joins the project must read this booklet, and anyone who reads the booklet joins the project.
Initially the chairperson holds all m booklets. The chairperson and anyone who receives at least one booklet first reads a booklet and, if they have subordinates, passes booklets to them. A subordinate is a person whose supervisor is that person. Each booklet can be passed to one of the subordinates. You may pass two or more booklets to the same subordinate, and some subordinates may receive no booklet. Once a booklet has been read, there is no need to keep it on hand.
Given each person's supervisor, each person's motivation value, and the number of booklets m, write a program that answers the maximum possible sum of the motivation values of the people who join the project.
Input
The first line of the input contains two integers n, m (1 ≤ n ≤ 10 000, 1 ≤ m ≤ 1000) separated by a space. This means the Japanese Olympiad in Informatics Committee has n people and the number of booklets made is m.
The next n lines give each person's supervisor and motivation value. The (i + 1)-th line (1 ≤ i ≤ n) contains two integers si, ai (0 ≤ si < i, 1 ≤ ai ≤ 10 000) separated by a space. This means person i's supervisor is person si and person i's motivation value is ai. If si is 0, person i is the chairperson. (Since si < i, a person's supervisor always has a number smaller than that person's number, and person 1 is always the chairperson.)
Output
Write the output to standard output. Print one integer, the maximum sum of the motivation values of the people who join the project.