洛谷P2015二叉苹果树

传送门啦

树形 $ dp $ 入门题，学树形 $ dp $ 的话，可以考虑先做这个题。

$ f[i][j] $ 表示在 $ i $ 这棵子树中选 $ j $ 个苹果的最大价值。

include

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 105;

inline int read(){
	char ch = getchar();
	int f = 1 , x = 0;
	while(ch > '9' || ch < '0'){if(ch == '-')f = -1;ch = getchar();}
	while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + ch - '0';ch = getchar();}
	return x * f;
}

int n,q,u,v,w;
int f[maxn][maxn],size[maxn];
int head[maxn],tot;

struct Edge{
	int to,from,val,next;
}edge[maxn << 1];

void add(int u,int v,int w){
	edge[++tot].from = u;
	edge[tot].to = v;
	edge[tot].val = w;
	edge[tot].next = head[u];
	head[u] = tot;
}

void dfs(int x,int fa){
	size[x] = 1;
	for(int i=head[x];i;i=edge[i].next){
		int v = edge[i].to;
		if(v != fa){
			dfs(v , x);
			size[x] += size[v];
			for(int j=min(size[x],q);j>=1;j--)
				for(int k=min(j-1,size[v]);k>=0;k--)
					f[x][j] = max(f[x][j] , f[x][j-k-1] + f[v][k] + edge[i].val);
		}
	}
}

int main(){
	n = read(); q = read();
	for(int i=1;i<=n-1;i++){
		u = read(); v = read(); w = read();
		add(u , v , w);
		add(v , u , w);
	}
	dfs(1 , 0);
	printf("%d
",f[1][q]);
	return 0;
}