2013年9月28日 星期六

1236 - Disjoint Paths

給一張圖,具有 N 個點和 N-1 條有權重的邊。找到最多 K 條不相交(點和邊皆不重複使用)的路徑,而所有被選上的邊權重總和最大。


如上如所示,兩個不同限制下,在相同的圖中會有不同的答案。

在不相交路徑最多 K 條時,當 K = 1,如左圖所示,答案最大為 13 (5+2+6)。

當 K = 2,如右圖所示,答案最大為 15 ((5+1)+(3+6))。

Input 

輸入第一行會有一個整數 T,表示接下來的測資組樹。

對於每組測資,第一行會有兩個整數 N, K (K <= N <= 60)。

接下來會有 N - 1 行,每行上會有三個整數 A, B, D,表示一條無向邊於 A 到 B 權重為 D。
(1 <= A, B <= N, |D| <= 10000)


Output 

對於每組測資,輸出最大總和。

Sample Input 

2 
6 1 
1 2 5
3 2 2
3 4 6
6 3 3
2 5 1
6 2 
1 2 5
3 2 2
3 4 6
6 3 3
2 5 1

Sample Output 

13 
15