Apple Tree POJ
题目链接：
D - 树形dp
题目大意：一颗树，n个点（1-n），n-1条边，每个点上有一个权值，求从1出发，走V步，最多能遍历到的权值
学习网址：https://blog.csdn.net/Aria461863631/article/details/82356420
具体思路：
dp[root][j][0]为从root出发，走j步并且最终回到原来点（中间也有可能回到原来的点，但是会继续往下走）的情况下，回到root节点的权值最大值。
dp[root][j][1]为从root出发，走j步并且最终不会到原来点（中间也有可能回到原来的点，但是会继续往下走）的情况下，回到root节点的权值最大值。
dp[root][j][0]=max(dp[root][j][0],dp[root][j-i][0]+dp[son][i-2][0]);
从当前的root出发，先计算从root开始走j-i步并且回到root的时候（遍历其他子树）的最大值，再加上走当前的son节点并且回来的时候最大值，
之所以是i-2的原因是，从s出发到t，然后从t再回到s，这一共是额外的两步，所以是i-2。
dp[root][j][1]=max(dp[root][j][1],dp[root][j-i][0]+dp[son][i-1][1]);
从当前的root出发，先计算从root出发走j-i步并且回到root的时候（遍历其他的子树）的最大值，在加上到达son，并且从son出发，不再回到root节点的最大值。
dp[root][j][1]=max(dp[root][j][1],dp[root][j-i][1]+dp[son][i-2][0]);
从当前root节点出发，先计算从root到son节点走i-2步并且回到root的时候的最大值，然后再去从root节点出发，到达剩余子树并且最终不回到root节点的最大值。
AC代码：
1 #include<iostream>
2 #include<stdio.h>
3 #include<cmath>
4 #include<algorithm>
5 #include<string>
6 #include<cstring>
7 #include<vector>
8 using namespace std;
9 # define ll long long
10 const int maxn = 2e5+100;
11 # define inf 0x3f3f3f3f
12 int dp[200+10][200+10][2];
13 int vis[maxn];
14 int sto[maxn];
15 vector<int>Edge[maxn];
16 int n,k;
17 void init()
18 {
19 for(int i=0; i<=n; i++)
20 {
21 vis[i]=0;
22 Edge[i].clear();
23 // for(int j=0; j<=k; j++)
24 // {
25 // dp[i][j][0]=0;
26 // dp[i][j][1]=0;
27 // }
28 }
29 }
30 void dfs(int u,int dep)
31 {
32 for(int i=0; i<=k; i++)
33 {
34 dp[u][i][0]=dp[u][i][1]=sto[u];
35 }
36 vis[u]=1;
37 for(int i=0; i<Edge[u].size(); i++)
38 {
39 int to=Edge[u][i];
40 if(vis[to])
41 continue;
42 dfs(to,dep-1);
43 for(int i1=k; i1>=1; i1--)
44 {
45 for(int i2=1; i2<=i1; i2++)
46
47 {
48 if(i2-2>=0)
49 dp[u][i1][0]=max(dp[u][i1][0],
50 dp[u][i1-i2][0]+dp[to][i2-2][0]);
51 if(i2-1>=0)
52 dp[u][i1][1]=max(dp[u][i1][1],
53 dp[u][i1-i2][0]+dp[to][i2-1][1]);
54 if(i2-2>=0)
55 dp[u][i1][1]=max(dp[u][i1][1],
56 dp[u][i1-i2][1]+dp[to][i2-2][0]);
57 }
58 }
59 }
60 }
61 int main()
62 {
63 while(~scanf("%d %d",&n,&k)){
64 int st,ed;
65 init();
66 for(int i=1; i<=n; i++){
67 scanf("%d",&sto[i]);
68 }
69 for(int i=1; i<n; i++){
70 scanf("%d %d",&st,&ed);
71 Edge[st].push_back(ed);
72 Edge[ed].push_back(st);
73 }
74 dfs(1,k);
75 printf("%d
",max(dp[1][k][1],dp[1][k][0]));
76 }
77 return 0;
78 }