题目大意
给出一棵树和树上的一些物品，每个物品有三个树形：价格，价值，库存。
选择一些物品购买使得价值最大，同时满足选择的物品在树上呈一个连通块。
题目分析
这里讲过的套路。
直接暴力从下往上转移会T，因此用点分治优化。
点分治得到重心，规定必须选择重心，递归重心延伸出的链，从上往下转移（强制选择）。
每次回溯的时候更新状态。
可以用二进制拆分或单调队列优化多重背包转移的过程，时间复杂度分别是$O(nm\log d\log n)$与$O(nm\log n)$。
没找到单调队列比二进制拆分慢很多的原因，可能是我代码写的丑，虚心求大佬教。
代码
二进制拆分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
using namespace std;
//二进制拆分
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=505,maxm=4005;
int t,n,m,Min,Core,Size[maxn],Maxson[maxn],f[maxn][maxm],ans=0;
bool vst[maxn];
vector<int>edges[maxn];
void AddEdge(int x,int y) {
edges[x].push_back(y);
}
void Get_Size(int Now,int father) {
Size[Now]=1;
Maxson[Now]=0;
for(int Next:edges[Now]) {
if(Next==father||vst[Next])continue;
Get_Size(Next,Now);
Size[Now]+=Size[Next];
Maxson[Now]=max(Maxson[Now],Size[Next]);
}
}
void Get_Core(int Now,int father,int num) {
Maxson[Now]=max(Maxson[Now],Size[num]-Size[Now]);
if(Maxson[Now]<Min) {
Min=Maxson[Now];
Core=Now;
}
for(int Next:edges[Now]) {
if(Next==father||vst[Next])continue;
Get_Core(Next,Now,num);
}
}
struct Thing {
int num,cost,value;
} a[maxn];
void zero_one_pack(int* f,Thing a,int k,int m) {
a.cost*=k,a.value*=k;
for(int j=m; j>=a.cost; j--)
f[j]=max(f[j],f[j-a.cost]+a.value);
}
void Dfs(int Now,int fa,int m) {
if(m<=0)return;
int num=a[Now].num-1,k=1;
while(k<num) {
zero_one_pack(f[Now],a[Now],k,m);
num-=k;
k<<=1;
}
zero_one_pack(f[Now],a[Now],num,m);
for(int Next:edges[Now]) {
if(vst[Next]||Next==fa)continue;
for(int j=0; j<=m-a[Next].cost; j++)f[Next][j]=f[Now][j]+a[Next].value;
Dfs(Next,Now,m-a[Next].cost);
for(int j=a[Next].cost; j<=m; j++)f[Now][j]=max(f[Now][j],f[Next][j-a[Next].cost]);
}
}
void Solve(int Now) {
Min=n;
Get_Size(Now,0);
Get_Core(Now,0,Now);
Now=Core;
vst[Now]=1;
for(int i=0; i<=m-a[Now].cost; i++)f[Now][i]=a[Now].value;
Dfs(Now,0,m-a[Now].cost);
for(int i=0; i<=m-a[Now].cost; i++)ans=max(ans,f[Now][i]);
for(int Next:edges[Now]) {
if(vst[Next])continue;
Solve(Next);
}
}
int main() {
t=Get_Int();
while(t--) {
n=Get_Int();
m=Get_Int();
for(int i=1; i<=n; i++)edges[i].clear();
for(int i=1; i<=n; i++)a[i].value=Get_Int();
for(int i=1; i<=n; i++)a[i].cost=Get_Int();
for(int i=1; i<=n; i++)a[i].num=Get_Int();
for(int i=1; i<n; i++) {
int x=Get_Int(),y=Get_Int();
AddEdge(x,y);
AddEdge(y,x);
}
ans=0;
memset(f,0,sizeof(f));
memset(vst,0,sizeof(vst));
Solve(1);
printf("%d\n",ans);
}
return 0;
}
单调队列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
using namespace std;
//单调队列
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=505,maxm=4005;
int t,n,m,Min,Core,Size[maxn],Maxson[maxn],f[maxn][maxm],ans=0;
bool vst[maxn];
vector<int>edges[maxn];
void AddEdge(int x,int y) {
edges[x].push_back(y);
}
void Get_Size(int Now,int father) {
Size[Now]=1;
Maxson[Now]=0;
for(int Next:edges[Now]) {
if(Next==father||vst[Next])continue;
Get_Size(Next,Now);
Size[Now]+=Size[Next];
Maxson[Now]=max(Maxson[Now],Size[Next]);
}
}
void Get_Core(int Now,int father,int num) {
Maxson[Now]=max(Maxson[Now],Size[num]-Size[Now]);
if(Maxson[Now]<Min) {
Min=Maxson[Now];
Core=Now;
}
for(int Next:edges[Now]) {
if(Next==father||vst[Next])continue;
Get_Core(Next,Now,num);
}
}
struct Thing {
int num,cost,value;
} a[maxn];
void trans(int* f,const Thing& a,int m) {
for(int mod=0; mod<a.cost; mod++) {
deque<pii>Q;
for(int i=0,index; (index=i*a.cost+mod)<=m; i++) {
while(!Q.empty()&&Q.front().first<i-a.num)Q.pop_front();
while(!Q.empty()&&Q.back().second<=f[index]-i*a.value)Q.pop_back(); //允许自己转移到自己
Q.push_back(mp(i,f[index]-i*a.value));
f[index]=Q.front().second+i*a.value;
}
}
}
void Dfs(int Now,int fa,int m) {
if(m<=0)return;
Thing tmp=a[Now];
tmp.num--;
trans(f[Now],tmp,m);
for(int Next:edges[Now]) {
if(vst[Next]||Next==fa)continue;
for(int j=0; j<=m-a[Next].cost; j++)f[Next][j]=f[Now][j]+a[Next].value;
Dfs(Next,Now,m-a[Next].cost);
for(int j=a[Next].cost; j<=m; j++)f[Now][j]=max(f[Now][j],f[Next][j-a[Next].cost]);
}
}
void Solve(int Now) {
Min=n;
Get_Size(Now,0);
Get_Core(Now,0,Now);
Now=Core;
vst[Now]=1;
for(int i=0; i<=m-a[Now].cost; i++)f[Now][i]=a[Now].value;
Dfs(Now,0,m-a[Now].cost);
for(int i=0; i<=m-a[Now].cost; i++)ans=max(ans,f[Now][i]);
for(int Next:edges[Now]) {
if(vst[Next])continue;
Solve(Next);
}
}
int main() {
t=Get_Int();
while(t--) {
n=Get_Int();
m=Get_Int();
for(int i=1; i<=n; i++)edges[i].clear();
for(int i=1; i<=n; i++)a[i].value=Get_Int();
for(int i=1; i<=n; i++)a[i].cost=Get_Int();
for(int i=1; i<=n; i++)a[i].num=Get_Int();
for(int i=1; i<n; i++) {
int x=Get_Int(),y=Get_Int();
AddEdge(x,y);
AddEdge(y,x);
}
ans=0;
memset(f,0,sizeof(f));
memset(vst,0,sizeof(vst));
Solve(1);
printf("%d\n",ans);
}
return 0;
}
