Pruning Trees

All submissions for this problem are available.
You have a tree (an acyclic, connected graph) with edge weights, but it is far too big. You are to prune the tree by deleting some edges so that the following property holds. For each connected component C of the pruned tree, there is some node r_{C} such that for every node v in C, the total weight of the edges on the path between v and r_{C} is at most some given value d.
You happen to like heavy trees so you want to delete the minimum possible total edge weight to satisfy this property.
Input
The first line of each test case is an integer T ≤ 40 indicating the number of test cases to follow. The first line of each test case contains two integers n and d that indicate there are n nodes in the tree and d is as specified in the problem description. Suppose the nodes in the tree are indexed by integers between 0 and n1. Then n1 lines follow, each containing three integers u,v, and w. This indicates that there is an edge of weight w between nodes u and v. The input will be such that the graph is connected with no cycles. No edge will be given more than once and no edge in the input will be a loop (i.e. u ≠ v for each input edge).
Bounds: 1 ≤ n ≤ 100, 0 ≤ d ≤ 10^{9}, and, for each edge u,v,w in the input, 0 ≤ u < v ≤ n1 and 1 ≤ w ≤ 10^{7}.
Output
The output for each test case consists of a single line containing a single integer denoting the maximum total weight of edges that can remain after deleting some edges so that the remaining graph satisfies the property described in the problem description.
Example
Input: 3 5 10 0 1 10 1 2 9 1 3 10 3 4 9 10 1 0 1 1 0 2 1 1 3 1 1 4 1 2 5 1 2 6 1 2 7 1 6 8 1 6 9 1 7 2 0 1 1 0 2 2 1 3 1 1 4 2 2 5 2 2 6 7 Output: 29 7 7
Author:  friggstad 
Tester:  pieguy 
Editorial  http://discuss.codechef.com/problems/PRUNING 
Tags  friggstad hard may11 
Date Added:  7012011 
Time Limit:  5 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.4, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
Can someone explain the tree
Can someone explain the tree structure more please...
totally confused about what we have to do..
Can someone clear the problem
Can someone clear the problem ?
For instance, the first example. Why we got the 29 as answer ?
There exists a subgraph of the given tree which has vertices V={0,1,2,3,4}, and edges E={(1,2), (3,4)}, and satisfies the given conditions. Obviously, to get such subgraph we need to remove two edges (0,1) and (1,3) with sum cost 20. Thus, the answer should be 20. Where is the mistake ?
@Kostia: You have to output
@Kostia: You have to output the "maximum total weight of edges that can remain after deleting some edges [...]", not the weight of the deleted edges.
There is something that i'm
There is something that i'm missing:
In the first example we can prune:
a) (1,3)
But the total weight from 0 to 2 its 19 > 10
or
b) (1,2)
But the total weight from 0 to 4 its 29 > 10
Both cases are the only prunes that i see to have a total weight of 29.
What i'm missing?
Read the condition you have
Read the condition you have to satisfy after pruning again. Just because the distance between 0 and 2 after pruning (1,3) is more than 10 doesn't mean that isn't valid.
can anyone expnain that how
can anyone expnain that how the answer of 2nd and 3rd test case is 7?
Stephen, will u please
Stephen, will u please explain how dose the output of 2nd or 3rd case is 7.
@anshuman for both cases
@anshuman
for both cases delete edge 01 and 26