Time Limit: 6000/3000 MS (Java/Others)

Memory Limit: 524288/524288 K (Java/Others)

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, \dots n}$ into $k$ parts $S_1, S_2, S_3, \dots S_k$,

where $\bigcup S_i = \{2, 3, \dots , n \}$ and for all different $i, j$ , we can conclude that $S_i \bigcap S_j = \emptyset$.

Then he calulates $res = \sum_{i = 1}^{k}{f(\{1\}\bigcup S_i)}$.

He wants to maximize the $res$.

$1\leq k\leq n\leq 10^6$

$\text{the cost of each edge} \in [1, 10^5]$

$S_i$ 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

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, \dots n}$ into $k$ parts $S_1, S_2, S_3, \dots S_k$,

where $\bigcup S_i = \{2, 3, \dots , n \}$ and for all different $i, j$ , we can conclude that $S_i \bigcap S_j = \emptyset$.

Then he calulates $res = \sum_{i = 1}^{k}{f(\{1\}\bigcup S_i)}$.

He wants to maximize the $res$.

$1\leq k\leq n\leq 10^6$

$\text{the cost of each edge} \in [1, 10^5]$

$S_i$ 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 \leq 100$.

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 \leq 100$.

提交代码