题解
好抽象啊,类背包问题,在增加一个根节点时,其最大值是由若干个子节点保留若干个树枝形成的
最关键的在于设二维数组把树枝的根数算在内,可能是因为以该节点为根节点的树保留q根树枝的最大值具有无后效性吧
而且答案需要用到其子节点保留q1,q2...(太抽象了)
code
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int> > G[105];
void add(int x,int y,int s)
{
G[x].push_back({y,s});
G[y].push_back({x,s});
}
int vis[105]={0};
int f[105][105]={0};
int n,q;
void ss(int now)
{
if(vis[now])return;
else vis[now]=1;
for(int i=0;i<G[now].size();i++)
{
int next=G[now][i].first,num=G[now][i].second;
if(vis[next])continue;
ss(next);
for(int k=q;k>=1;k--)//k代表以now节点为根的树有几根树枝
for(int j=0;j<k;j++)//j代表以子节点为根的数有几根树枝,有可能是0,譬如叶子节点;不可能是k,因为还要连now节点
f[now][k]=max(f[now][k],f[now][k-j-1]+num+f[next][j]);//类背包,f[now][k-j-1]时为什么要减一?因为此时next节点一定没用到
}
}
int main()
{
cin>>n>>q;
for(int i=1;i<n;i++)
{
int x,y,s;
cin>>x>>y>>s;
add(x,y,s);//不知道哪个是父节点
}
ss(1);
cout<<f[1][q]<<endl;//好抽象啊
return 0;
}