hdu6566(树背包+轻链剖分)

|

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=6566

题意

给定 $n$ 个点的树，每个节点有权值 $ai$ 、$b_i$ ，选定独立点集 $S$ ，令 $A(S)=\sum{i\in S} ai$ ，$B(S)=\sum{i\in S}b_i$ ，定义 $f(x)$ 为满足 $A(s)=x$ 的所有 $S$ 中最大的 $B(S)$ 的个数

题解

好题。。

一个显然的解法是直接做树背包，然而复杂度是 $O(nm^2)$

发现背包合并的复杂度过大，所以需要将点依次加进背包中，所以考虑将树转化成序列，在 $DFS$ 序上做背包。。

对整棵树做轻链剖分，在 $DP$ 的时候先走轻儿子，设 $d[i][S][j]$ 为到第 $i$ 个点，状态为 $S$ ，背包容量为 $j$ 的最大的 $B(S)$ 及其个数

$S$ 表示的是 $i$ 到根路径上各个重链头的父亲和 $i$ 自己是否在独立集内，即每个链上都在转接点处保留当前点的状态，由于链的个数只有 $\log n$ 个，那么 $S$ 的大小也只有 $2^{\log n}=n$ 个

这个做法的巧妙之处就是，将转接点处的点的状态保存了下来，所以我们只要管当前重链的转移情况就可以了，然后合并的时候也只需要按我们所分的不同的情况直接取个 $MAX$ 即可。。

那么转移的时候要分 $4$ 种情况考虑

  1. 从重链转移向轻儿子
  2. 沿着重链往下走
  3. 从轻儿子往重儿子转移
  4. 从轻儿子往轻儿子转移




代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
/**
 *　　　　　　  　　┏┓　　 　┏┓
 * 　　　　　  　　┏┛┗━━━━━━━┛┗━━━┓
 * 　　　　　  　　┃　　　　　　　┃ 　
 * 　　　　　  　　┃　　　━　　 　┃
 * 　　　　　  　　┃　＞　　　＜　┃
 * 　　　　　  　　┃　　　　　　　┃
 * 　　　　　  　　┃...　⌒　... 　┃
 * 　　　　　　  　┃              ┃
 * 　　　　　　  　┗━┓          ┏━┛
 * 　　　　　　　　　┃          ┃　Code is far away from bug with the animal protecting　　　　　　　　　　
 * 　　　　　　　　　┃          ┃   神兽保佑,代码无bug
 * 　　　　　　　　　┃          ┃　　　　　　　　　　　
 * 　　　　　　　　　┃          ┃  　　　　　　
 * 　　　　　　　　　┃          ┃
 * 　　　　　　　　　┃          ┃　　　　　　　　　　　
 * 　　　　　　　　　┃          ┗━━━┓
 * 　　　　　　　　　┃              ┣┓
 * 　　　　　　　　　┃              ┏┛
 * 　　　　　　　　　┗┓┓┏━━━━━━━━┳┓┏┛
 * 　　　　　　　　　　┃┫┫       ┃┫┫
 * 　　　　　　　　　　┗┻┛       ┗┻┛
 */ 
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<set>
#include<bitset>
#include<complex>
#include<cstdlib>
#include<assert.h>
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,l,r) for(int i=l;i>=r;i--)
#define link(x) for(edge *j=h[x];j;j=j->next)
#define mem(a) memset(a,0,sizeof(a))
#define ll long long
#define eps 1e-8
#define succ(x) (1<<x)
#define lowbit(x) (x&(-x))
#define mid (x+y>>1)
#define sqr(x) ((x)*(x))
#define NM 55
#define nm 5005
const double pi=acos(-1);
const int inf=10007;
using namespace std;
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return f*x;
}
 

struct edge{int t;edge*next;}e[NM<<1],*h[NM],*o=e;
void add(int x,int y){o->t=y;o->next=h[x];h[x]=o++;}
int n,m,a[NM],b[NM],_x,_y,ca,_t;
int f[NM],size[NM],c[NM],id[NM],tot,son[NM],cnt[NM];

void dfs1(int x){
    size[x]=1;
    link(x)if(j->t!=f[x]){
	f[j->t]=x;
	dfs1(j->t);
	size[x]+=size[j->t];
	if(size[son[x]]<size[j->t])son[x]=j->t;
    }
}
void dfs2(int x,int t){
    id[x]=++tot;c[tot]=x;cnt[tot]=t;
    link(x)if(j->t!=f[x]&&j->t!=son[x])dfs2(j->t,t+1);
    if(son[x])dfs2(son[x],t);
}

struct P{ll x,y;}d[2][NM][nm],ans[nm];
inline void upd(P&a,const P b){if(b.y)if(a.x<b.x)a=b;else if(a.x==b.x)a.y+=b.y;}
inline void upd(P&a,const P b,const int k){if(b.y)if(a.x<b.x+k)a=b,a.x+=k;else if(a.x==b.x+k)a.y+=b.y;}

int main(){
    int _=read();while(_--){
	mem(son);tot=0;mem(ans);mem(h);o=e;mem(f);mem(size);mem(c);mem(id);mem(cnt);mem(e);
	n=read();m=read();
	inc(i,1,n)a[i]=read(),b[i]=read();
	inc(i,2,n){_x=read();_y=read();add(_x,_y);add(_y,_x);}
	dfs1(1);dfs2(1,1);
	mem(d[0]);
	d[_t=0][0][0].y=1;
	inc(i,1,n){
	    _t^=1;mem(d[_t]);
	    const int x=a[c[i]],y=b[c[i]];
	    if(f[c[i]]==c[i-1]){
		if(cnt[i]==cnt[i-1]){
		    inc(j,0,succ(cnt[i])-1)if(j&1){
			inc(k,x,m)upd(d[_t][j][k],d[_t^1][j^1][k-x],y);
		    }else{
			inc(k,0,m)upd(d[_t][j][k],d[_t^1][j][k]),upd(d[_t][j][k],d[_t^1][j^1][k]);
		    }
		}else{
		    inc(j,0,succ(cnt[i])-1)if(j%4==3)continue;
		    else if(j&1){
			inc(k,x,m)upd(d[_t][j][k],d[_t^1][j>>1][k-x],y);
		    }else{
			inc(k,0,m)upd(d[_t][j][k],d[_t^1][j>>1][k]);
		    }
		}
	    }else{
		if(cnt[i]<cnt[i-1]){
		    inc(j,0,succ(cnt[i])-1)if(j&1){
			inc(_j,((j^1)<<(cnt[i-1]-cnt[i])),(( j<<(cnt[i-1]-cnt[i]) )-1) )
			    inc(k,x,m)upd(d[_t][j][k],d[_t^1][_j][k-x],y);
		    }else{
			inc(_j,(j<<(cnt[i-1]-cnt[i]) ),(( (j+2) << (cnt[i-1]-cnt[i]) )-1 ) )
			    inc(k,0,m)upd(d[_t][j][k],d[_t^1][_j][k]);
		    }
		}else{
		    inc(j,0,succ(cnt[i])-1)if(j%4==3)continue;
		    else if(j&1){
			inc(_j,(j^1),j)
			    inc(k,x,m)upd(d[_t][j][k],d[_t^1][_j][k-x],y);
		    }else{
			inc(_j,j,(j^1))
			    inc(k,0,m)upd(d[_t][j][k],d[_t^1][_j][k]);
		    }
		}
	    }
	}
	inc(j,0,succ(cnt[n])-1)inc(k,1,m)upd(ans[k],d[_t][j][k]);
	printf("Case %d:\n",++ca);
	inc(i,1,m)printf("%lld%c",ans[i].y," \n"[i==m]);
    }
    return 0;
}