「SDOI2017」苹果树 - 树上依赖背包+多重背包 | Bill Yang's Blog

「SDOI2017」苹果树 - 树上依赖背包+多重背包

题目大意

    夏天近了,又到了恋爱的季节,小 Q 家门前的苹果树上结满了红红圆圆的苹果。

    这株苹果树是一个有着$n$个结点的有根树,其中结点被依次编号为$1$至$n$。$1$号结点为根,其余每一个结点的父结点一定是某个编号较小的结点。每一个结点上都有一些苹果,第$i$个结点上有$a_i(a_i>0)$个苹果,每取走其中一个苹果就可以得到$v_i(v_i\gt0)$的幸福度(若在这个结点取走$k\leq a_i$个苹果,则可以收获$kv_i$的幸福度)。如果在一个结点取走了至少一个苹果,则必须要在其父结点处取走至少一个苹果。

    现在,给定正整数$k$,请从树上取走若干苹果。如果总计取走了$t$个苹果,且所有取了至少一个苹果的那些结点的最大深度为$h$(这里规定根结点的深度为$1$),则要求$t-h\le k$。问最大可以收获多少的幸福度?(这些幸福度全都归属于恋爱中的小 Q)


题目分析

分析限制$t-h\le k$,可以理解为允许免费选择一条最长链,然后剩下的做依赖背包。
显然,这条免费的最长链肯定延伸到叶子结点最优(点权为正),设选择的叶子结点为$end$。
如图,我们将选出的物品以免费最长链为分界分为三部分:

最长链左上方的是第一部分(dfs序小于$end$的点),最长链是第二部分,最长链右下方是第三部分(dfs序大于$end$的点)。

第一部分沿着正Dfs序放物品。
先放不能免费的物品,遍历完所有儿子后加入必选物品。
这样,$i$到根的路径只算了不能免费的部分。

第三部分沿着逆Dfs序放物品。
先遍历所有儿子,然后放入必选的和不能免费的。

这样,使用一二三部分的和更新答案即可。


代码

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {
if(x=='-')bj=-1;
x=getchar();
}
while(isdigit(x)) {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=20005,maxnm=26000005;
int n,m,Wid,Len,f[maxnm],g[maxnm],fa[maxn],ans=0;
vector<int> edges[maxn];
void AddEdge(int x,int y) {
edges[x].push_back(y);
}
struct Thing {
int num,value;
} a[maxn];
#define pii pair<int,int>
#define mp make_pair
void trans(int *f,const Thing& a) {
deque<pii>Q;
for(int i=0; i<=m; i++) {
while(!Q.empty()&&Q.front().first<i-a.num)Q.pop_front();
while(!Q.empty()&&Q.back().second<=f[i]-i*a.value)Q.pop_back();
Q.push_back(mp(i,f[i]-i*a.value));
f[i]=Q.front().second+i*a.value;
}
}
void Dfs1(int Now) {
if(a[Now].num)trans(f+Now*Wid,a[Now]);
for(int Next:edges[Now]) {
memcpy(f+Next*Wid,f+Now*Wid,Len);
Dfs1(Next);
for(int j=1,*p=f+Now*Wid+1,*q=f+Next*Wid; j<=m; j++,p++,q++)*p=max(*p,*q+a[Next].value);
}
}
void Dfs2(int Now,int sum) {
sum+=a[Now].value;
for(int Next:edges[Now]) {
memcpy(g+Next*Wid,g+Now*Wid,Len);
Dfs2(Next,sum);
for(int j=1,*p=g+Now*Wid+1,*q=g+Next*Wid; j<=m; j++,p++,q++)*p=max(*p,*q+a[Next].value);
}
if(!edges[Now].size())for(int j=0,*p=f+Now*Wid+m,*q=g+Now*Wid; j<=m; j++,p--,q++)ans=max(ans,*p+*q+sum);
if(a[Now].num)trans(g+Now*Wid,a[Now]);
}
void Clear() {
for(int i=1; i<=n; i++)edges[i].clear();
memset(f+Wid,0,Len);
memset(g+Wid,0,Len);
ans=0;
}
int main() {
int t=Get_Int();
while(t--) {
Clear();
n=Get_Int();
m=Get_Int();
Wid=m+1;Len=Wid*sizeof(int);
for(int i=1; i<=n; i++) {
fa[i]=Get_Int();
if(fa[i])AddEdge(fa[i],i);
a[i].num=Get_Int()-1;
a[i].value=Get_Int();
}
Dfs1(1);
for(int i=1; i<=n; i++)edges[i].clear();
for(int i=n; i>=1; i--)if(fa[i])AddEdge(fa[i],i);
Dfs2(1,0);
printf("%d\n",ans);
}
return 0;
}
本篇文章有用吗?有用还不快点击!
0%