Pruning Trees

Problem code: PRUNING

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 rC such that for every node v in C, the total weight of the edges on the path between v and rC 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 n-1. Then n-1 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 ≤ 109, and, for each edge u,v,w in the input, 0 ≤ u < v ≤ n-1 and 1 ≤ w ≤ 107.

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
Date Added: 7-01-2011
Time Limit: 5 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

Can someone explain the tree

sak3t @ 1 May 2011 11:15 PM

Can someone explain the tree structure more please...

totally confused about what we have to do..

Can someone clear the problem

k0stia @ 2 May 2011 08:10 PM

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

theluy @ 2 May 2011 08:32 PM

@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

gareve @ 5 May 2011 08:14 AM

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

triplem @ 5 May 2011 08:34 AM

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

anshuiiita @ 5 May 2011 10:44 AM

can anyone expnain that how the answer of 2nd and 3rd test case is 7?

Stephen, will u please

anshuiiita @ 5 May 2011 05:26 PM

Stephen, will u please explain how dose the output of 2nd or 3rd case is 7.

@anshuman for both cases

demo @ 8 May 2011 09:56 PM

@anshuman

for both cases delete edge 0-1 and 2-6

SUCCESSFUL SUBMISSIONS


Fetching successful submissions