The Hanged Man(HDU 6566)
题意
\(n\)个点的树，每个点有两种权值\(a_i,b_i\)。你需要选出一个独立集，使得\(a_i\)的总和恰好为\(m\)，并且\(b_i\)的总和尽量大。同时你需要计算这些独立集的数量。
做法
可以轻易地想到\(O(nm^2)\)的树形背包，但显然过不去，考虑优化
看到本题有不少用\(dfs\)序+树剖优化\(dp\)的，但其实并没有很大的必要
我们可以先找出树的重心，再在子树内部进行搜索，得到每棵子树每种情况下的\(a_i\)和与\(b_i\)和，最后再将每棵子树和重心的答案合并起来
现在问题来了，菊花图下合并\(n\)棵子树不照样是\(n^2\)的吗？
那当然，所以为了解决这个问题，我们需要引入一个优化，
去除无效状态
我们可以发现，明明菊花图下每棵子树只有\(1\)种情况，但我们还是要傻乎乎地进行\(m\)次\(O(m)\)的背包更新，于是我们可以考虑记录下存在的情况，再进行更新
时间复杂度证明
可以知道，大小为\(x\)的树想要 匹配方案数(不一定为最大匹配) 最多，那么最坏情况一定为 链
可以得出匹配方案数\(f_n=f_{n-1}+f_{n-2}\),为斐波那契数
所以时间复杂度为\(O((\sum_{x\in S}f_x)+m\sum_{x\in S}\min(f_x,m))[(\sum_{x\in S}x)=n]\)
当\(f_x\)均等于\(m\)时取最大值，
最坏情况为\(m=5000,n=50,x=20\),运行次数\(≈ 62500000\)
但实际效率飞快，\(\text{hdu}\)上为\(202ms\)
\(\mathfrak{Talk\ is\ cheap,show\ you\ the\ code.}\)
#include<bits/stdc++.h>
using namespace std;
# define ll long long
# define read read1<ll>()
# define Type template<typename T>
Type T read1(){
T t=0;char k;bool vis=0;
do (k=getchar())=='-'&&(vis=1);while('0'>k||k>'9');
while('0'<=k&&k<='9')t=(t<<3)+(t<<1)+(k^'0'),k=getchar();
return vis?-t:t;
}
int s,m,sz[55],R,M,f[2][55][5005],h[2][55][5005],w[2][55][5005],tx,ty,a[55],b[55],dp[2][2][5005],d[55];
ll wh[2][2][5005];
vector<int>G[55];
void dfs(int n,int f){
sz[n]=1;int x=0;
for(int i=0;i<G[n].size();++i)
if(G[n][i]!=f){
dfs(G[n][i],n);
sz[n]+=sz[G[n][i]];
x=max(x,sz[G[n][i]]);
}x=max(x,s-sz[n]);
if(x<M)R=n,M=x;
}
vector<int>tn;
void pre(int x,int fa){
tn.push_back(x);d[x]=fa;
for(int i=0;i<G[x].size();++i)
if(G[x][i]!=fa)pre(G[x][i],x);
}bool vis[55];
void dfs1(int o,int u,bool x){
if(u==tn.size()){
if(!w[x][o][tx])h[x][o][++h[x][o][0]]=tx;
if(f[x][o][tx]<ty)f[x][o][tx]=ty,w[x][o][tx]=0;
if(f[x][o][tx]==ty)++w[x][o][tx];
return;
}
dfs1(o,u+1,x);
if(!vis[d[tn[u]]]&&tx+a[tn[u]]<=m){
vis[tn[u]]=1;
tx+=a[tn[u]];ty+=b[tn[u]];
dfs1(o,u+1,x);vis[tn[u]]=0;
tx-=a[tn[u]];ty-=b[tn[u]];
}
}
int main(){
for(int T=read,V=0;T--;){
s=read,m=read;M=2e9;
for(int i=1;i<=s;++i)G[i].clear(),a[i]=read,b[i]=read;
for(int i=1;i<s;++i){
int u=read,v=read;
G[u].push_back(v);
G[v].push_back(u);
}dfs(1,0);
memset(f,0,sizeof(f));memset(w,0,sizeof(w));
memset(dp[0],0,sizeof(dp[0]));memset(wh[0],0,sizeof(wh[0]));
wh[0][0][0]=wh[0][1][a[R]]=1;
dp[0][1][a[R]]=b[R];
for(int i=0;i<G[R].size();++i){
h[0][i][0]=h[1][i][0]=0;
tn.clear();pre(G[R][i],R);
vis[R]=1;dfs1(i,0,1);
vis[R]=0;dfs1(i,0,0);
memset(dp[1],0,sizeof(dp[1]));
memset(wh[1],0,sizeof(wh[1]));
for(int j=1;j<=h[0][i][0];++j){
int x=h[0][i][j];
for(int k=x;k<=m;++k)
if(wh[0][0][k-x]){
if(dp[1][0][k]<dp[0][0][k-x]+f[0][i][x]){
dp[1][0][k]=dp[0][0][k-x]+f[0][i][x];
wh[1][0][k]=0;
}
if(dp[1][0][k]==dp[0][0][k-x]+f[0][i][x])
wh[1][0][k]+=w[0][i][x]*wh[0][0][k-x];
}
}
for(int j=1;j<=h[1][i][0];++j){
int x=h[1][i][j];
for(int k=x;k<=m;++k)
if(wh[0][1][k-x]){
if(dp[1][1][k]<dp[0][1][k-x]+f[1][i][x]){
dp[1][1][k]=dp[0][1][k-x]+f[1][i][x];
wh[1][1][k]=0;
}
if(dp[1][1][k]==dp[0][1][k-x]+f[1][i][x])
wh[1][1][k]+=w[1][i][x]*wh[0][1][k-x];
}
}
memcpy(dp[0],dp[1],sizeof(dp[0]));
memcpy(wh[0],wh[1],sizeof(wh[0]));
}
printf("Case %d:\n",++V);
for(int i=1;i<=m;++i){
printf("%lld",dp[0][0][i]<dp[0][1][i]?wh[0][1][i]:(dp[0][0][i]>dp[0][1][i]?wh[0][0][i]:wh[0][0][i]+wh[0][1][i]));
putchar(i==m?'\n':' ');
}
}
return 0;
}