树形DP
一开始想：f[i][j]表示以 i 为根的子树，花 j 块钱能得到的最高力量值，结果发现转移的时候没法保证叶子结点的数量限制TAT
只好去膜拜题解了……在这里贴两篇泛型背包的文章吧：《背包九讲》、徐持衡《浅谈几类背包题》
vfk的酷炫姿势没看懂……这篇题解应该讲的是比较清楚的一篇>_> http://blog.csdn.net/baidu_20126217/article/details/40086029
这题算是把我对树形DP的闭塞理解给打通了一点。
我本认为树形DP只有用子节点的状态去更新父节点的状态，真是太天真了。
实际上这道题里是用子节点的状态合并得到父节点的状态。
首先，设出状态f[i][j][k]表示节点i对父亲的贡献为j付出的代价为k时i节点及其子树可以得到的最多能量。
dp当然要从初始状态推起咯。
那么对于那些叶子节点，也就是所谓的基本装备:
f[i][j][j*cost[i]]=(j-i)*power[i]
然而对于那些非叶子节点:
f[i][j][k]=max{g[k-r]+f[son][j*need[son]][r]};
这个方程具体点的解释可以理解为预算为k，拨给这个项目经费为r。
注意在这里我们并没有对f[i][j][k]中这一层中“私吞”部分进行统计，所以是j*need[son]，也就是假设全部先上交。
此处g数组是对上一次f[i][j]的复制，防止出现值的误调用。
此处循环考虑的因素比较多，所以总不能一边调用f[i][j]一边更新f[i][j]吧。memcpy多方便。
然后我们开始统计私吞部分:
f[i][j][k]=max{f[i][j'][k]+(j'-j)*power[i]}
事实上,(j'-j)*power[i]就是没有用于合成(即上交)的i装备产生的能量。
非常巧妙，可惜这状态我想不到，还是经验问题。
Tips:注意挖掉一些非法状态和缩小lim范围。
/**************************************************************
Problem: 1017
User: Tunix
Language: C++
Result: Accepted
Time:8236 ms
Memory:48576 kb
****************************************************************/ //BZOJ 1017
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
inline int getint(){
int v=,sign=; char ch=getchar();
while(ch<''||ch>''){ if (ch=='-') sign=-; ch=getchar();}
while(ch>=''&&ch<=''){ v=v*+ch-''; ch=getchar();}
return v*sign;
}
const int N=,INF=~0u>>;
typedef long long LL;
/******************tamplate*********************/
int n,m,ans=-INF;
struct node{int to,v;};
vector<node>G[N];
int f[N][][],g[],cost[N],num[N],str[N],fa[N];
void dfs(int x){
if (!G[x].size()){
num[x]=min(num[x],m/cost[x]);
F(i,,num[x])
F(j,i,num[x])
f[x][i][j*cost[x]]=(j-i)*str[x];
return;
}//DP边界：叶子结点
num[x]=INF;
rep(i,G[x].size()){
dfs(G[x][i].to);
// cost[x]+=cost[G[x][i].to]*G[x][i].v;
num[x]=min(num[x],num[G[x][i].to]/G[x][i].v);
}//预处理合成装备的num和cost
F(i,,num[x]) f[x][i][]=;
rep(i,G[x].size()){
int to=G[x][i].to;
F(j,,num[x]){
memcpy(g,f[x][j],sizeof f[x][j]);
memset(f[x][j],-,sizeof f[x][j]);
D(k,m,){
D(r,k,)
if (g[k-r]!=- && f[to][j*G[x][i].v][r]!=-)
f[x][j][k]=max(f[x][j][k],g[k-r]+f[to][j*G[x][i].v][r]);
ans=max(ans,f[x][j][k]);
}
}
}
F(i,,num[x]) F(j,i,num[x]) F(k,,m)
if (f[x][j][k]!=-)
f[x][i][k]=max(f[x][i][k],f[x][j][k]+(j-i)*str[x]),
ans=max(ans,f[x][i][k]);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("1017.in","r",stdin);
freopen("1017.out","w",stdout);
#endif
n=getint(); m=getint();
F(i,,n){
fa[i]=i;
num[i]=INF;
cost[i]=;
}
char s1[];
F(i,,n){
str[i]=getint();
scanf("%s",s1);
if (s1[]=='B'){
cost[i]=getint();
num[i]=getint();
}else{
int c=getint();
F(j,,c){
int x=getint(),y=getint();
G[i].pb((node){x,y});
fa[x]=i;
}
}
}
int root=;
F(i,,n) if (fa[i]==i){root=i;break;}
memset(f,-,sizeof f);
dfs(root);
printf("%d\n",ans);
return ;
}