刷题记录:POJ - 2486Apple Tree

传送门:Vjudge

题目描述:

Wshxzt is a lovely girl. She likes apple very much. One day HX takes her to an apple tree. There 
are N nodes in the tree. Each node has an amount of apples. Wshxzt starts her happy trip at one 
node. She can eat up all the apples in the nodes she reaches. HX is a kind guy. He knows that 
eating too many can make the lovely girl become fat. So he doesn’t allow Wshxzt to go more than 
K steps in the tree. It costs one step when she goes from one node to another adjacent node. 
Wshxzt likes apple very much. So she wants to eat as many as she can. Can you tell how many 
apples she can eat in at most K steps.
输入:
2 1 
0 11
1 2
3 2
0 1 2
1 2
1 3
输出:
11
2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

一道树形背包dp的难题,建议即使不会也记忆一下其解法

主要思路:

1. 对于树形dp, 我们先观察一下对于我们的结点$u$和它的当前枚举到的子树$v$我们在树上的行走最后有几种状态,我们发现大致有以下几类:
2. 第一类:经过u的除v之外的所有子树,然后回到u,然后再经过我们的v子树,然后回到u
3. 第二类:经过u的除v之外的所有子树,然后回到u然后枚举我们的子树v,但是此时停留在我们的v子树上
4. 第三类:经过u的v子树,然后回到u,然后再枚举u的其他子树,但是最后停在其他子树上
5. 我们可以使用$dp[u][j][0/1]$来记录我们的u节点使用了了$j$步没有回到$/$回到我们的$u$结点的最大获得

那么对于我们的第一类情况,我们可以使用背包的思想来记录每一个子树的最优值

$dp[u][j][1]=max(dp[u][j-t][1]+dp[v][t-2][1])$

此时假设我们在V子树上走了J步,但是如果是以我们的$v$作为结点的话,那么我们将花两步在在我们的$v$结点和$u$结点至今的边上
对于为什么我们的$dp[u][j-k][1]$能代表我们的其他节点,这是因为我们是使用我们的背包思想的,虽然我们在刚开始枚举子树时我们并没有枚举完我们的其他子树,但是我们使用的是背包的方法,我们在逐渐的枚举过程中每一次都保存的是当前已经枚举完的所有子树,所以在正确性上时没有任何问题的

对于我们的第二类情况,同理可以写出第二类的dp方程:

$dp[u][j][0]=max(dp[u][j][0],dp[u][j-t][1]+dp[v][t-1][0])$

对于我们的第三类情况,同样可以写出:

$dp[u][j][0]=max(dp[u][j][0],dp[u][j-t][0]+dp[v][t-2][1])$

---

下面是具体的代码部分:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
int dp[300][300][3];
vector<int>edge[maxn];int a[maxn];
int n,k;
void dfs(int u,int pre_u) {
	for(int i=0;i<=k;i++) {
		dp[u][i][0]=dp[u][i][1]=a[u];//赋初值
	}
	for(int i=0;i<edge[u].size();i++) {
		int v=edge[u][i];
		if(v==pre_u) continue;
		dfs(v,u);
		for(int j=k;j>=1;j--) {//树形背包dp
			for(int t=1;t<=j;t++) {
				dp[u][j][0]=max(dp[u][j][0],dp[v][t-1][0]+dp[u][j-t][1]);
				if(t>=2) {
					dp[u][j][1]=max(dp[u][j][1],dp[u][j-t][1]+dp[v][t-2][1]);
					dp[u][j][0]=max(dp[u][j][0],dp[u][j-t][0]+dp[v][t-2][1]);
				}
			}
		}
	}
	return ;
}
int main() {
	while(scanf("%d%d",&n,&k)!=EOF) {
		memset(dp,0,sizeof(dp));
		memset(a,0,sizeof(a));
		for(int i=1;i<=n;i++) edge[i].clear();
		for(int i=1;i<=n;i++) {
			a[i]=read();
		}
		int u,v;
		for(int i=1;i<=n-1;i++) {
			u=read();v=read();
			edge[u].push_back(v);
			edge[v].push_back(u);
		}
		dfs(1,0);
		printf("%d\n",max(dp[1][k][0],dp[1][k][1]));
	}
	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