ACM-ICPC-OJ训练营

问题 E: RXD and dividing

时间限制: 6 Sec 内存限制: 128 MB
提交: 14 解决: 10
[提交][状态][讨论版][命题人:]

题目描述

RXD has a tree

T, with the size of

n. Each edge has a cost.
Define

f(S) as the the cost of the minimal Steiner Tree of the set

S on tree

T.
he wants to divide

2,3,4,5,6,…n into

k parts

S1,S2,S3,…Sk,
where

⋃Si={2,3,…,n} and for all different

i,j , we can conclude that

Si⋂Sj=∅.
Then he calulates

res=∑ki=1f({1}⋃Si).
He wants to maximize the

res.

1≤k≤n≤106

the cost of each edge∈[1,105]

Si might be empty.

f(S) means that you need to choose a couple of edges on the tree to make all the points in

S connected, and you need to minimize the sum of the cost of these edges.

f(S) is equal to the minimal cost

There are several test cases, please keep reading until EOF.
For each test case, the first line consists of 2 integer

n,k, which means the number of the tree nodes , and

k means the number of parts.
The next

n−1 lines consists of 2 integers,

a,b,c, means a tree edge

(a,b) with cost

c.
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≤100.

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