Submit Best Submissions All Submissions

337. Mario and Evil Toad

Problem Statement:
Mario is trying to save Princess Peach from the evil Bowser. But at the end of every level, a small mushroom guy called Toad tells him that she is at a different castle. Mario suspects that Toad is actually evil, and keeps sending Mario to the furthest castle possible just for fun.

Mario's world can be modeled as a tree with N nodes (a tree of N nodes is a connected graph with N-1 edges, nodes are numbered from 1 to N), where each node represents a castle, and each edge represents a level. Mario starts his journey at the root of the tree, and travels around the tree (possibly passing the same nodes and edges several times) looking for the Princess in castles, according to the directions of Toad. It takes Mario a certain amount of time to cross a level (and it is the same in both direction).

Toad picks K distinct castles (the root isn't one of them), and Mario must visit them in the exact given order (Mario must start and end his tour at the root). Mario always takes the shortest path when going from one node to another. What is the maximum possible duration of Mario's journey if Toad had picked the worst possible K castles?

Input Format:
Your program will be tested on one or more test cases. The first line of the input will be a single integer T (1 ≤ T ≤ 100) representing the number of test cases. Followed by T test cases. Each test case starts with a line containing 2 integers N and K (2 ≤ N ≤ 1,000) (1 ≤ K ≤ 100) (1 ≤ K ≤ N - 1) representing the total number of castles in the tree and the number of castles Mario has to visit. Followed by N-1 lines, each line describes the nodes 2 to N. Each line will contain 2 integers Pi and Ci (1 ≤ Pi ≤ N) (0 ≤ Ci ≤ 100,000) representing the parent of the i-th node (i starts from 2 here) and the time it takes to pass the edge connecting the current node to its parent. Node 1 is the root of the tree.

Output Format:
For each test case print a single line containing "Case n:" (without quotes) where n is the test case number (starting from 1) followed by a space, followed by the maximum duration for Mario's journey.

Sample Input:
3 3 1 1 5 1 3 4 2 1 5 1 3 3 2 5 3 1 5 1 3 3 2 3 10

Sample Output:
Case 1: 10 Case 2: 20 Case 3: 46

For the third test case, one of the possible lists that Toad could have given Mario is following: 5, 2, 4.

Added by: ahmed_aly
Added at: 2014-11-20 22:34:43 UTC
Time Limit: 15 seconds
Partial score: No
Source:ACM Arab Collegiate Programming Contest 2014