시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 512 MB | 133 | 52 | 30 | 32.609% |
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 ui and vi and has length li. 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 p1, p2, . . . , pk that maximize Σdis(pi, pi mod k+1). Output the maximum sum.
The first line contains an integer T (1 ≤ T ≤ 105) indicating the number of test cases. For each test case:
The first line contains two integers n, k (2 ≤ n ≤ 2 · 105, 2 ≤ k ≤ n).
Each of the following n − 1 lines contains three integers ui, vi, li (1 ≤ ui, vi ≤ n, 1 ≤ li ≤ 106).
It is guaranteed that Σn ≤ 2 · 105.
For each test case, output one line with one integer: the answer.
1 5 3 1 2 4 1 3 1 1 4 8 4 5 9
44