#P7460. [2017年杭电多校]RXD and dividing

    ID: 7473 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 5 上传者: 标签>CF1800普及+/提高-贡献法DFS 序子树转区间序列构造

[2017年杭电多校]RXD and dividing

RXD and dividing

Problem Description

RXD has a tree TT, with the size of nn. Each edge has a cost. Define f(S)f(S) as the the cost of the minimal Steiner Tree of the set SS on tree TT. he wants to divide 2,3,4,5,6,…n{2, 3, 4, 5, 6, \dots n} into kk parts S1,S2,S3,…SkS_1, S_2, S_3, \dots S_k, where ⋃Si={2,3,…,n}\bigcup S_i = \{2, 3, \dots , n \} and for all different i,ji, j , we can conclude that Si⋂Sj=∅S_i \bigcap S_j = \emptyset. Then he calulates res=∑i=1kf({1}⋃Si)res = \sum_{i = 1}^{k}{f(\{1\}\bigcup S_i)}. He wants to maximize the resres. 1≤k≤n≤1061\leq k\leq n\leq 10^6 the cost of each edge∈[1,105]\text{the cost of each edge} \in [1, 10^5] SiS_i might be empty. f(S)f(S) means that you need to choose a couple of edges on the tree to make all the points in SS connected, and you need to minimize the sum of the cost of these edges. f(S)f(S) is equal to the minimal cost

Input

There are several test cases, please keep reading until EOF. For each test case, the first line consists of 2 integer n,kn, k, which means the number of the tree nodes , and kk means the number of parts. The next n−1n - 1 lines consists of 2 integers, a,b,ca, b, c, means a tree edge (a,b)(a, b) with cost cc. It is guaranteed that the edges would form a tree. There are 4 big test cases and 50 small test cases. small test case means n≤100n \leq 100.

Output

For each test case, output an integer, which means the answer.

Sample Input

5 4

1 2 3

2 3 4

2 4 5

2 5 6

Sample Output

27

Source

2017 Multi-University Training Contest - Team 3

https://acm.hdu.edu.cn/showproblem.php?pid=6060