Path in a graph is defined to be disjoint if there is no common edge and vertex that belongs to more than one path. Given a connected graph with N nodes and N - 1 weighted edges, we are interested in finding a set of up to K paths in the graph which are disjoint to each other. The set of paths should be chosen so that the sum of all weight of edges of the paths is the maximum possible.

The example above shows two configurations of disjoint paths in the same graph. When the limit of paths to be drawn (K ) is one (shown on the left), the maximum sum of all the weight of its edges is 13 (5+2+6). However, when we are allowed to draw up to 2 disjoint paths, we can draw two paths whose sum of edge weights evaluates to 15 (shown on the right).

Input 

The input begins with a line containing an integer T , the number of test cases follow. Each case begins with two non-negative integers N and K (KN60) . The next N - 1 following lines each will contains three integers: A , B and D ( 1A, BN ; and | D|10000 ) which means that there is an undirected edge from node A to node B with weight D .

Output 

For each case, print in a single line the maximum possible sum of weight of up to K disjoint paths in the given graph.

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

雖然 AC 了，但是跑的速度非常慢，可以考慮將背包 DP 那邊優化一下個數。

#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
struct edge {
	int to, w;
	edge(int a=0, int b=0):
		to(a), w(b) {}
};
int N, K;
vector<edge> g[65];
int zero[65][65];
int one[65][65];
int two[65][65];
int size[65];
int dfs(int nd, int p) {
	int i, j, k, x, y, z;
	for(i = 0; i <= K; i++)
		zero[nd][i] = one[nd][i] = two[nd][i] = -0xfffffff; 
	zero[nd][0] = 0;
	for(x = 0; x < g[nd].size(); x++) {
		if(g[nd][x].to == p)	continue;
		size[nd] += dfs(g[nd][x].to, nd);
	}
	// zero
	for(x = 0; x < g[nd].size(); x++) {
		int son = g[nd][x].to, sonw = g[nd][x].w;
		if(son == p)	continue;
		for(j = K; j >= 0; j--) {
			for(i = 0; i <= K; i++) {
				int mm = max(zero[son][i], max(one[son][i], two[son][i]));
				if(j-i >= 0)
					zero[nd][j] = max(zero[nd][j], zero[nd][j-i]+mm);
			}
		}
	}
	// one, make path to son.
	for(x = 0; x < g[nd].size(); x++) {
		int sonx = g[nd][x].to, sonxw = g[nd][x].w;
		if(sonx == p)	continue;
		int dp[65] = {};
		for(i = 1; i <= K; i++)
			dp[i] = -0xfffffff;
		for(y = 0; y < g[nd].size(); y++) {
			int sony = g[nd][y].to, sonyw = g[nd][y].w;
			if(sony == p) continue;
			if(sony == sonx)	continue;// important
			for(j = K; j >= 0; j--) {
				for(i = 0; i <= K; i++) {
					int mm = max(zero[sony][i], max(one[sony][i], two[sony][i]));
					if(j-i >= 0)
						dp[j] = max(dp[j], dp[j-i]+mm);
				}
			}
		}
		for(i = 0; i <= K; i++) {
			for(j = 0; i+j <= K; j++) {
				one[nd][i+j] = max(one[nd][i+j], dp[i]+one[sonx][j]+sonxw);	
				one[nd][i+j+1] = max(one[nd][i+j+1], dp[i]+zero[sonx][j]+sonxw);
			}
		}
	}
	//two, make a path through this node, between two son.
	for(x = 0; x < g[nd].size(); x++) {
		int sonx = g[nd][x].to, sonxw = g[nd][x].w;
		if(sonx == p)	continue;
		for(y = x+1; y < g[nd].size(); y++) {
			int sony = g[nd][y].to, sonyw = g[nd][y].w;
			if(sony == p || sony == sonx) continue;
			int dp[65] = {};
			for(i = 1; i <= K; i++)
				dp[i] = -0xfffffff;
			for(z = 0; z < g[nd].size(); z++) {
				int sonz = g[nd][z].to, sonzw = g[nd][z].w;
				if(sonz == p || sonz == sonx || sonz == sony)
					continue;
				for(j = K; j >= 0; j--) {
					for(i = 0; i <= K; i++) {
						int mm = max(zero[sonz][i], max(one[sonz][i], two[sonz][i]));
						if(j-i >= 0)
							dp[j] = max(dp[j], dp[j-i]+mm);
					}
				}
			}
			//printf("choose %d %d\n", sonx, sony);
			for(i = 0; i <= K; i++) {
				//printf("%d %d ***\n", i, dp[i]);
				for(j = 0; j <= K; j++) {
					for(k = 0; k <= K && i+j+k-1 <= K; k++) {
						if(j && k)// j != 0, k != 0
							two[nd][i+j+k-1] = max(two[nd][i+j+k-1], dp[i]+one[sonx][j]+one[sony][k]+sonxw+sonyw);
						//else if(j == 0 && k)
							two[nd][i+j+k] = max(two[nd][i+j+k], dp[i]+zero[sonx][j]+one[sony][k]+sonxw+sonyw);
						//else if(k == 0 && j)
							two[nd][i+j+k] = max(two[nd][i+j+k], dp[i]+one[sonx][j]+zero[sony][k]+sonxw+sonyw);							
						//else
							two[nd][i+j+k+1] = max(two[nd][i+j+k+1], dp[i]+zero[sonx][j]+zero[sony][k]+sonxw+sonyw);
					}
				}
			}
		}
	}
	//for(i = 1; i <= K; i++)
	//	printf("%d %d : %d %d %d\n", nd, i, zero[nd][i], one[nd][i], two[nd][i]);
	return size[nd];
}
int main() {   
	//freopen("in.txt","r+t",stdin);
    //freopen("out2.txt","w+t",stdout);
	int testcases;
	int i, j, k;
	int x, y, v;
	scanf("%d", &testcases);
	while(testcases--) {
		scanf("%d %d", &N, &K);
		for(i = 1; i <= N; i++)
			g[i].clear(), size[i] = 1;
		for(i = 1; i < N; i++) {
			scanf("%d %d %d", &x, &y, &v);
			g[x].push_back(edge(y, v));
			g[y].push_back(edge(x, v));
		}
		dfs(1, 0);
		int ret = 0;
		for(i = 1; i <= K; i++)
			ret = max(ret, max(zero[1][i], max(one[1][i], two[1][i])));
		printf("%d\n", ret);
	}
	return 0;
}
/*
10
10 3
1 2 92
2 3 1
1 4 81
1 5 52
5 6 83
1 7 97
2 8 11
8 9 90
1 10 43
10 5
1 2 76
1 3 23
3 4 61
1 5 30
2 6 16
5 7 26
2 8 52
6 9 90
6 10 72
10 8
1 2 66
2 3 19
2 4 60
1 5 78
2 6 25
3 7 84
4 8 -920
8 9 93
6 10 21
*/