Medium Divide and Conquer > Dynamic Programming

Asif is a very good businessman and he is very friendly and warm towards all of his employees . But he notices that some of them take this as an advantage and aren’t serious about their job . So keeping them in work aren’t beneficial for the company . He wants to sack them . The company has N employees . They are numbered from 1 to N and as a CEO of the company Asif’s id is 0 . The company maintains tree- like hierarchy . Each employee works under a supervisor . The CEO has no supervisor . Each employee report directly to his supervisor . If his supervisor is sacked from his job there is no means to keep him in the job too . You have a description of all employees , his supervisor id , his salary and productivity . The company gets profit from his service as his productivity minus( - ) his salary . Note that **it can be negative** . Company’s total profit is the sum of the profit It gets from all of his active employees. Can you tell the maximum profit the company can get after firing ( possibly none , possible all ) some of its employees. Input: ------ The first line contains an integer T ( 1 <= T <= 50 ) denotes the number of test cases. T test cases follow. There is a integer N ( 1 <= N <= 100 ) number of employees in the first line of every test case . Then N lines follow . Each line contains a description of each employee , Three integer numbers x ( his supervisor’s id , can be any of 0 to N ) , y ( his salary ) and z ( his productivity ) . . Output: ------- For each test case, print a line “Case x: y” where x is replaced by the test case number and y is the maximum profit the company can get . Constraints: ------- 1 <= T <= 50 1 <= N <=100 1 <= y <= 100000 1 <= z <= 100000 Sample Input ------------ 3 3 0 1 3 0 2 2 0 3 1 4 0 3 4 1 5 3 2 2 3 3 1 4 1 0 1 0 Sample Output ------------- Case 1: 2 Case 2: 3 Case 3: 0

Shakil Ahmed