一波树上背包秒杀……

#include
    
     #include
     
      #include
      
       #include
       
        #define REP(i, a, b) for(int i = (a); i < (b); i++)using namespace std;const int MAXN = 312;int f[MAXN][MAXN], cnt[MAXN], n, k;struct node{ int v, w; };vector
        
          g[MAXN];void dfs(int u, int fa){	REP(i, 0, g[u].size())	{		int v = g[u][i].v, w = g[u][i].w;		if(v == fa) continue;		dfs(v, u);		cnt[u] += cnt[v];		for(int j = cnt[u]; j >= 1; j--)			REP(k, 1, min(cnt[v], j - 1) + 1)				f[u][j] = max(f[u][j], f[u][j-k] + f[v][k] + w);	}}int main(){	scanf("%d%d", &n, &k);	REP(i, 1, n)	{		int u, v, w;		scanf("%d%d%d", &u, &v, &w);		g[u].push_back(node{v, w});		g[v].push_back(node{u, w});		cnt[i] = 1;	}	cnt[n] = 1;		dfs(1, -1);	printf("%d\n", f[1][k + 1]);		return 0;}