BZOJ第一页做着做着就能碰到毒题，做到BZOJ1082小C就忍了，没想到下一题就是这种东西。这种题目不拖出来枭首示众怎么对得起小C流逝的青春啊。
Description
DotR (Defense of the Robots) Allstars是一个风靡全球的魔兽地图，他的规则简单与同样流行的地图DotA (Defense of the Ancients) Allstars。DotR里面的英雄只有一个属性——力量。他们需要购买装备来提升自己的力量值，每件装备都可以使佩戴它的英雄的力量值提高固定的点数，所以英雄的力量值等于它购买的所有装备的力量值之和。装备分为基本装备和高级装备两种。基本装备可以直接从商店里面用金币购买，而高级装备需要用基本装备或者较低级的高级装备来合成，合成不需要附加的金币。装备的合成路线可以用一棵树来表示。比如，Sange and Yasha的合成需要Sange,Yasha和Sange and Yasha Recipe Scroll三样物品。其中Sange又要用Ogre Axe, Belt of Giant Strength和 Sange Recipe Scroll合成。每件基本装备都有数量限制，这限制了你不能无限制地合成某些性价比很高的装备。现在，英雄Spectre有M个金币，他想用这些钱购买装备使自己的力量值尽量高。你能帮帮他吗？他会教你魔法Haunt（幽灵附体）作为回报的。
Input
第一行包含两个整数，N 和 M 。分别表示装备的种类数和金币数。装备用1到N的整数编号。接下来的N行，按照装备1到装备N的顺序，每行描述一种装备。每一行的第一个非负整数表示这个装备贡献的力量值。接下来的非空字符表示这种装备是基本装备还是高级装备，A表示高级装备，B表示基本装备。如果是基本装备，紧接着的两个正整数分别表示它的单价（单位为金币）和数量限制（不超过100）。如果是高级装备，后面紧跟着一个正整数C，表示这个高级装备需要C种低级装备。后面的2C个数，依次描述某个低级装备的种类和需要的个数。
Output
第一行包含一个整数S，表示最多可以提升多少点力量值。
Sample Input
10 59
5 A 3 6 1 9 2 10 1
1 B 5 3
1 B 4 3
1 B 2 3
8 A 3 2 1 3 1 7 1
1 B 5 3
5 B 3 3
15 A 3 1 1 5 1 4 1
1 B 3 5
1 B 4 3
Sample Output
33
HINT
1 <= N <= 51，0 <= M <= 2000，数量限制不超过100。保证答案在int范围内。
Solution
刚开始做的时候，小C真的是麻了很久，依赖性问题这种东西不用状压怎么还能做的啊喂！
但是小C想了想，依赖关系构成了一棵树，不同子树之间的关系互不影响。仔细想想好像就能做了啊。
然后小C设计了f[i][j][k]表示在子树i内，强制取j个i，总共花k块钱能得到的最优答案。
搞了个O(N*100^2*M^2)的DP，然后发现好像可以分步优个化，复杂度变为O(N*100*M^2)。
然后小C实在想不出更优的复杂度了，再加上迷之原因一直WA，无奈之下去看题解。
可没想到，（网络上大部分）题解的复杂度，就他喵的是这个啊！！！
然后跑去看discuss，发现有全是B类装备的情况，那一瞬间小C内心有千万只*奔腾而过。
喂说好的树呢？玩文字游戏有意思吗？这么出数据不怕走路被古明地盆砸吗？？
然后就过了……但小C还是不甘心，听说vfleaking还有新做法，赶紧去膜了一发，发现确实神。
（vfleaking大爷好像也是借鉴别人的代码，但他似乎是小C所能找到的最早的把这种做法发表出来的人，所以膜他还是没有错的）
题解传送门：http://vfleaking.blog.163.com/blog/static/17480763420130242646240/。
为了阐述简洁，小C就按照原题解的说法，默认每个DP数组后面自带[0..m]，表示花费的金币数。
设energy[x]为x提供的能量，money[x]为x的花费，limit[x]为x最多能取多少个，needsum[x]为x的父亲需要几个x合成，fa[x]为x的父亲。
我们从最初想到的状态“f[i][j]表示在子树i内，强制取j个i，能得到的最优答案”入手，把状态改进一下。
因为如果不是在根结点，求得的f数组都是没什么用的。
然后改进状态：opt[i][j]表示在子树i内，强制取j个不产生贡献的i，能得到的最优答案。
乍一看和原来的状态设计没有什么两样嘛！然而继续往下看就会发现它的好处。
然后最终答案就是opt[root][0]。
定义运算（A,B,C都是[0..m]数组）：
①C=merge(A,B)，表示C[i]=max(A[j]+B[i-j]) (0<=j<=i<=m)；
②C=merge(A)^k，表示C=merge(A,A,..,A) (k个A)。
考虑opt[i][j]怎么转移：设g[i]为在子树i内取总需求不超过相当于一个i的量的装备得到的最优答案。
所以opt[i][j]=merge(opt[i][j+1],g[i])。
考虑g[i]怎么转移：g[i]=merge(merge(g[u1])^needsum[u1] , merge(g[u2])^needsum[u2] , ... , merge(g[ut])^needsum[ut])（u1,u2,...,ut为i的儿子）。
别忘了用energy[i]更新g[i][money[i]]。
因为opt[i][j]的转移是按照j从大到小的顺序来的，j最大是limit[i]。
考虑opt[i][limit[i]]怎么求：opt[i][limit[i]]=merge(opt[u1][limit[i]*needsum[u1]] , opt[u2][limit[i]*needsum[u2]] , ... , opt[ut][limit[i]*needsum[ut]])。
所以设f[x]=opt[x][limit[fa[x]]*needsum[x]]。
结合上面的转移，由于一定有limit[x]>=limit[fa[x]]*needsum[x]，所以f[x]→opt[fa[x]][limit[fa[x]]]→f[fa[x]]，就可以实现f的转移了。
所以最终答案就是f[root]=opt[root][0]，这是小C认为最神的地方。
小C看了看好像理论复杂度上限好像也是O(100*N*M^2)？求g的部分是100*N*M^2，求f的部分好像只有100*M^2？
然而这种做法的常数巨小，复杂度远远不及上限，加了几个小优化后甚至复杂度还是科学的呢？
VFK大爷的解法（第二种）：
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MN 55
#define MM 2005
using namespace std;
struct edge{int nex,to;}e[MN];
int n,m,p,pin,rt,ans,INF;
int lm[MN],mon[MN],f[MN][MM],g[MN][MM],w[MN],hr[MN],nds[MN],fa[MN],h[MM];
bool u; inline int read()
{
int n=,f=; char c=getchar();
while (c<'' || c>'') {if(c=='-')f=-; c=getchar();}
while (c>='' && c<='') {n=n*+c-''; c=getchar();}
return n*f;
} inline void ins(int x,int y) {e[++pin]=(edge){hr[x],y}; hr[x]=pin;}
inline bool rw(int& x,int y) {if (y>x) {x=y; return true;} else return false;} bool merge(int *A,int* B,int AL,int BL)
{
register int i,j,lt=INF;
bool fg=false;
if (AL>m) AL=m;
if (BL>m) BL=m;
for (i=AL;i>=;--i)
{
if (A[i]==INF) continue;
for (j=;j<=BL&&i+j<=AL;++j)
if (B[j]!=INF) if (rw(A[i+j],A[i]+B[j])) fg=true;
if (B[]==INF) A[i]=INF;
}
for (i=;i<=AL;++i)
if (A[i]<=lt) A[i]=INF; else lt=A[i];
return fg;
} void dp(int x)
{
register int i,j,k,l,lim;
if (!hr[x])
{
for (i=nds[x]*lm[fa[x]];i<=lm[x];++i)
f[x][(i-nds[x]*lm[fa[x]])*mon[x]]=(i-nds[x]*lm[fa[x]])*w[x];
g[x][]=; if (mon[x]<=m) g[x][mon[x]]=w[x];
return;
}
g[x][]=f[x][]=;
for (i=hr[x];i;i=e[i].nex)
{
dp(e[i].to);
for (j=;j<=nds[e[i].to];++j)
if (!merge(g[x],g[e[i].to],mon[x],mon[e[i].to])) break;
merge(f[x],f[e[i].to],m,m);
}
if (mon[x]<=m) rw(g[x][mon[x]],w[x]);
for (i=lm[fa[x]]*nds[x];i<lm[x];++i) merge(f[x],g[x],m,mon[x]);
} void dfs(int x)
{
if (hr[x]) lm[x]=m;
for (register int i=hr[x];i;i=e[i].nex) dfs(e[i].to);
lm[x]=min(lm[x],m/mon[x]);
if (nds[x])
lm[fa[x]]=min(lm[fa[x]],lm[x]/nds[x]),
mon[fa[x]]+=mon[x]*nds[x];
} int main()
{
register int i,j,k,x,y;
char gh[];
n=read(); m=read();
for (i=;i<=n;++i)
{
w[i]=read();
scanf("%s",gh);
if (gh[]=='A')
for (p=read(),u=true;p;--p)
x=read(),nds[x]=read(),fa[x]=i,ins(i,x);
else if (gh[]=='B') mon[i]=read(),lm[i]=read();
}
memset(f,,sizeof(f));
memset(g,,sizeof(g));
INF=f[][]; ans=;
if (!u)
{
memset(h,,sizeof(h)); h[]=;
for (i=;i<=n;++i)
for (j=m;j>=;--j)
for (k=;k<=lm[i];++k)
if (k*mon[i]<=j && h[j-k*mon[i]]!=INF)
rw(h[j],h[j-k*mon[i]]+k*w[i]);
for (i=;i<=m;++i) rw(ans,h[i]);
return *printf("%d",ans);
}
for (i=;i<=n;++i) if (!fa[i]) {rt=i; break;}
dfs(rt); dp(rt);
for (i=;i<=m;++i) rw(ans,f[rt][i]);
printf("%d",ans);
}
小C的丑陋解法（第一种）：
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MN 55
#define MS 105
#define MM 2005
using namespace std;
struct edge{int nex,to,wt;}e[MN];
int n,m,p,pin,rt,ans,INF;
int lm[MN],mon[MN],f[MN][MS][MM],g[MN][MM],w[MN],hr[MN],h[MM];
bool d[MN],u; inline int read()
{
int n=,f=; char c=getchar();
while (c<'' || c>'') {if(c=='-')f=-; c=getchar();}
while (c>='' && c<='') {n=n*+c-''; c=getchar();}
return n*f;
} inline void ins(int x,int y,int z) {e[++pin]=(edge){hr[x],y,z}; hr[x]=pin;} void dp(int x)
{
register int i,j,k,l,lim;
if (lm[x])
{
lm[x]=min(lm[x],m/mon[x]);
for (i=;i<=lm[x];++i)
for (j=i;j<=lm[x];++j)
f[x][i][j*mon[x]]=j*w[x];
return;
}
for (i=hr[x];i;i=e[i].nex)
{
dp(e[i].to);
mon[x]+=mon[e[i].to]*e[i].wt;
lm[x]=m/mon[x];
lm[x]=min(lm[x],lm[e[i].to]/e[i].wt);
}
for (i=lm[x];i>=;--i)
{
lim=mon[x]*i; f[x][i][]=;
for (j=hr[x];j;j=e[j].nex)
{
for (;lm[e[j].to]>=i*e[j].wt;--lm[e[j].to])
for (l=mon[e[j].to]*lm[e[j].to];l<=m;++l)
g[e[j].to][l]=max(g[e[j].to][l],f[e[j].to][lm[e[j].to]][l]);
for (k=m;k>=(i==);--k)
{
if (i>) f[x][i][k]=INF;
for (l=mon[e[j].to]*i*e[j].wt;l<=k;++l)
if (f[x][i][k-l]!=INF&&g[e[j].to][l]!=INF)
f[x][i][k]=max(f[x][i][k],f[x][i][k-l]+g[e[j].to][l]-i*e[j].wt*w[e[j].to]);
}
}
for (j=;j<=m;++j) if (f[x][i][j]!=INF) f[x][i][j]+=i*w[x];
}
} int main()
{
register int i,j,k,x,y;
char gh[];
n=read(); m=read();
for (i=;i<=n;++i)
{
w[i]=read();
scanf("%s",gh);
if (gh[]=='A')
for (p=read(),u=true;p;--p)
x=read(),y=read(),ins(i,x,y),d[x]=true;
else if (gh[]=='B') mon[i]=read(),lm[i]=read();
}
memset(f,,sizeof(f));
memset(g,,sizeof(g));
INF=f[][][]; ans=;
if (!u)
{
memset(h,,sizeof(h)); h[]=;
for (i=;i<=n;++i)
for (j=m;j>=;--j)
for (k=;k<=lm[i];++k)
if (k*mon[i]<=j && h[j-k*mon[i]]!=INF)
h[j]=max(h[j],h[j-k*mon[i]]+k*w[i]);
for (i=;i<=m;++i) ans=max(h[i],ans);
return *printf("%d",ans);
}
for (i=;i<=n;++i) if (!d[i]) {rt=i; break;}
dp(rt);
for (i=;i<=lm[rt];++i)
for (j=;j<=m;++j) ans=max(ans,f[rt][i][j]);
printf("%d",ans);
}
Last Word
只放图不说话。