P2015 二叉苹果树
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
int dp[101][101];
int mp[1001][1001];
struct NO{
int w,to,nxt;
}no[501];
int cnt,sid[101];
int head[101];
int q,n;
int book[101];
void add(int u,int v,int w){
cnt;
no[cnt].to = v; no[cnt].w = w;
no[cnt].nxt = head[u];
head[u] = cnt;
}
void dfs(int u,int fa){
for(int l=head[u];l;l=no[l].nxt){
int v = no[l].to;
if(v==fa)continue;
dfs(v,u); sid[u] =sid[v] 1;
for(int i=min(sid[u],q);i>0;i--)
for(int j=min(sid[v],i-1);j>=0;j--){
dp[u][i] = max(dp[u][i],dp[u][i-j-1] dp[v][j] no[l].w);
}
}
}
int main()
{
scanf("%d %d",&n,&q);
memset(head,0,sizeof(head));
for(int i=0;i<n-1;i )
{
int u,v,w;
scanf("%d %d %d",&u,&v,&w);
add(u,v,w); add(v,u,w);
}
dfs(1,-1);
printf("%dn",dp[1][q]);
return 0;
} 
