406045: GYM102222 G Factories

Byteland has $$$n$$$ cities numbered from $$$1$$$ to $$$n$$$, and $$$n-1$$$ bi-directional roads connecting them. For each pair of cities, the residents can arrive one from another one through these roads (which also means the road network in Byteland is a tree).

Ghaliyah, the queen of the land, has decided to construct $$$k$$$ new factories. To avoid contamination, she requires that a factory can locate at a city with only one road (which also means this city is a leaf in the road network). Besides, a city can only have one factory.

You, as the royal designer, are appointed to arrange the construction and meanwhile, minimize the sum of distances between every two factories.

The input contains several test cases, and the first line is a positive integer $$$T$$$ indicating the number of test cases which is up to $$$10^3$$$.

For each test case, the first line contains two integers $$$n~(2\le n \le 10^5)$$$ and $$$k~(1 \le k \le 100)$$$ indicating the number of cities in Byteland and the number of new factories which are asked to construct.

Each of the following $$$n-1$$$ lines contains three integers $$$u, v~(1\le u,v\le n)$$$ and $$$w~(1 \le w \le 10^5)$$$ which describes a road between the city $$$u$$$ and the city $$$v$$$ of length $$$w$$$.

We guarantee that the number of leaves in the road network is no smaller than $$$k$$$, and the sum of $$$n$$$ in all test cases is up to $$$10^6$$$.

For each test case, output a line containing Case #x: y, where x is the test case number starting from $$$1$$$, and y is the minimum sum of distances between every two factories.

2
4 2
1 2 2
1 3 3
1 4 4
4 3
1 2 2
1 3 3
1 4 4

Case #1: 5
Case #2: 18