18755번 - Cyclic Distance

The trick from problem “Alien” is a great way to improve a naive O(nk) dynamic programming to O(n log n). More problems with this trick can make the contest better, like the two unsolved problems in 300iq Contest 2.

You are given a weighted tree with n vertices and n − 1 edges. The i-th edge connects vertices u_i and v_i and has length l_i. Let dis(u, v) be the distance (sum of weights on simple path) between vertex u and vertex v in the tree.

Find k distinct vertices p₁, p₂, . . . , p_k that maximize Σdis(p_i, p_{i mod k+1}). Output the maximum sum.

The first line contains an integer T (1 ≤ T ≤ 10⁵) indicating the number of test cases. For each test case:

The first line contains two integers n, k (2 ≤ n ≤ 2 · 10⁵, 2 ≤ k ≤ n).

Each of the following n − 1 lines contains three integers u_i, v_i, l_i (1 ≤ u_i, v_i ≤ n, 1 ≤ l_i ≤ 10⁶).

It is guaranteed that Σn ≤ 2 · 10⁵.

For each test case, output one line with one integer: the answer.