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;
}
# define fre(k) freopen(k".in","r",stdin);freopen(k".out","w",stdout)
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]]);
		}
	if(f)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;
}