Tasks:
 
Task DescriptionDiscussion (0)
Task :: z-company
Mister Little Z sometimes imagines that z-trening is a big company with a lot of employees with a pyramidal structure (Big Boba is the main boss, and every employee has its own boss).

One day Little Z was planning a party for his imaginary employees. Little Z know the value of presents each of the employees would bring to the party. However, due to the crisis the employee-boss relations in the company are not very good, so Z wants to invite only some of the employees so that:

- No employee and his boss are at the party
- He maximizes the value of the presents brought to the party

INPUT:
From the first line of the standard input read an integer N (1 <= N <= 100000). The employee with index 0 is Big Boba - the main boss. From the next (second) line read one integer V representing the value of the present that Big Boba would bring to the party. From the next N-1 lines read the information about the rest N-1 employees, from each of the two lines read two integers B and V, where B is the 0-based index of the corresponding employee, and V is the value of the present they would bring to the party. We have 0 <= B < N and 1 <= V <= 1000000.

OUTPUT:
To the standard output write one integer representing the maximal value of presents mister Little Z can get at his imaginary party

Input:
4
1
0 2
0 1
2 2

Output:
4

Explanation employees with indices 1 and 3 would be invited

Input:
5
1
0 2
0 1
1 2
2 2

Output:
5

Explanation employees with indices 0, 3 and 4 would be invited
Submit Solution
:
:
Available Languages
Task info
Name:z-company
Time:0.25 sec.
Memory:16 MB
#Tests:10
AddedBy: admin
Task Ratings
Difficulty:

3.9 (9 votes)
Quality:

3.7 (9 votes)
Acceptance Rate
Recent Submissions
Fastest Solutions
UserTime
bl4ck.c0d3r 0.13 s.
ivan100sic 0.133 s.
Al3kSaNdaR 0.139 s.
vdmedragon 0.151 s.
halil 0.163 s.
tsebayoth 0.166 s.
PetarV 0.167 s.
zare2000 0.17 s.
ortschun 0.178 s.
frank44 0.178 s.
Solved By