洛谷 P2015 二叉苹果树 题解

时间:2021-03-15 08:18:43

题面

裸的树上背包:

设f[u][i]表示在以u为子树的树种选择i条边的最大值,则:f[u][i]=max(f[u][i],f[u][i-j-1]+f[v][k]+u到v的边权);

#include <bits/stdc++.h>
using namespace std;
struct littlestar{
int to;
int nxt;
int w;
}star[];
int head[],cnt;
void add(int u,int v,int w)
{
star[++cnt].to=v;
star[cnt].nxt=head[u];
star[cnt].w=w;
head[u]=cnt;
}
int f[][];
int d[];
int n,q;
void dfs(int u,int fa)
{
for(int i=head[u];i;i=star[i].nxt){
int v=star[i].to;
if(v==fa) continue;
dfs(v,u);
d[u]+=d[v]+;
for(int j=min(d[u],q);j>=;j--){
for(int k=min(d[v],j-);k>=;k--){
f[u][j]=max(f[u][j],f[u][j-k-]+f[v][k]+star[i].w);
}
}
}
}
int main()
{
cin>>n>>q;
for(int i=;i<n;i++)
{
int x,y,w;
scanf("%d%d%d",&x,&y,&w);
add(x,y,w);
add(y,x,w);
}
dfs(,);
cout<<f[][q];
}