题目链接：

D - 树形dp

 POJ - 2486 

题目大意：一颗树，n个点（1-n），n-1条边，每个点上有一个权值，求从1出发，走V步，最多能遍历到的权值

学习网址：https://blog.csdn.net/Aria461863631/article/details/82356420

具体思路：dp[i][j][0]代表当前的i点在只走一边的情况下，往下走j部最多能获得的权值。

               dp[i][j][1]代表当前的点在两边都走的情况下，往下走j不最多能获得的权值。

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\n",max(dp[1][k][1],dp[1][k][0]));
76     }
77     return 0;
78 }