这题我的思路是树形dp+多重背包，状态跟别人不大一样。我的状态表示 $F[i][j]$ 表示恰好装满节点 $i$ 的子树容积为 $j$ 的背包，物品是每个儿子的 $F[1\sim n]$ 为一组。

大家如有时间请帮忙看看，谢谢

#include <bits/stdc++.h>
using namespace std;
int n,m,b[205],f[205][205],siz[205],fa[205];
string str[205];
vector<int> G[205];
map<string,int> trl;
void DP(int step){
	if(G[step].size()==0){
		f[step][1]=b[step];
		siz[step]=1;
		return;
	}
	f[step][0]=0;
	for(int i=0;i<G[step].size();i++){
		DP(G[step][i]);
		siz[step]+=siz[G[step][i]];
	}
	siz[step]++;
	for(int i=0;i<G[step].size();i++)
		for(int j=n;j>=0;j--)
			for(int k=1;k<=n;k++) if(j>=k)
				f[step][j]=min(f[step][j],f[step][j-k]+f[G[step][i]][k]);
	f[step][siz[step]]=min(f[step][siz[step]],b[step]);
}
int find(int x){
	return x==fa[x]?x:fa[x]=find(fa[x]);
}
void unite(int x,int y){
	fa[find(x)]=find(y);
}
int main()
{
	while(cin>>n>>m){
		getchar();
		
		memset(b,0,sizeof(b));
		memset(siz,0,sizeof(siz));
		trl.clear();
		
		for(int i=1;i<=n;i++){
			G[i].clear();
			getline(cin,str[i]);
			string tmp="";
			for(int j=0;j<str[i].length() && str[i][j]!=' ';j++) tmp+=str[i][j];
			trl[tmp]=i;
		}
		for(int i=1;i<=n+1;i++)fa[i]=i;
		for(int i=1;i<=n;i++){
			int j=0;
			string tmp="";
			for(;j<str[i].length() && str[i][j]!=' ';j++);
			for(j++;j<str[i].length() && str[i][j]>='0' && str[i][j]<='9';j++) b[i]=b[i]*10+str[i][j]-'0';
			for(j++;j<str[i].length();j++){
				if(str[i][j]==' '){
					G[i].push_back(trl[tmp]);
					unite(trl[tmp],i);
					tmp="";
					continue;
				}
				tmp+=str[i][j];
			}
			if(tmp!=""){
				G[i].push_back(trl[tmp]);
				unite(trl[tmp],i);
			}
		}
		set<int>s;for(int i=1;i<=n;i++)s.insert(find(i));
		for(set<int>::iterator it=s.begin();it!=s.end();it++) G[n+1].push_back(*it);
		memset(f,0x3f,sizeof(f));
		b[n+1]=0x3f3f3f3f;
		DP(n+1);
		int ans=0x3f3f3f3f;
		for(int i=m;i<=n;i++) ans=min(ans,f[n+1][i]);
		cout<<ans<<endl;
		/*for(int i=1;i<=n+1;i++,puts("")) for(int j=1;j<=n;j++) cout<<f[i][j]<<' ';*/
	}
	return 0;
} 
/*
错误数据：
20 11
Anland 64
Alland 56
Ajland 35
Ahland 66
Baland 87 Ajland
Aeland 19 Alland
Abland 52
Bcland 38
Amland 87
Bbland 17 Bcland
Afland 22 Amland
Agland 97 Ahland
Aaland 74 Aeland Agland
Akland 8 Aaland
Bdland 32 Abland
Adland 98 Akland
Beland 86 Afland Adland
Acland 58 Beland
Aoland 4 Acland
Ailand 92 Aoland
*/