苹果树(多维树形dp)

 1 /*************************************************************************
 2   > Author: Henry Chen
 3   > Mail: 390989083@qq.com 
 4   > Created Time: 涓? 8/26 21:33:15 2020
 5  ************************************************************************/
 6 #include<bits/stdc++.h>
 7 using namespace std;
 8 int dp[110][210][2];
 9 int val[110];
10 vector<int>vec[110];
11 int n,k;
12 void dfs(int u,int fa)
13 {
14     //printf("dfs %d
",u);
15     for(int i = 0;i < vec[u].size();i++)
16     {
17         int v = vec[u][i];
18         if(v == fa) continue;
19         dfs(v,u);
20         for(int j = k;j >= 0;j--)
21         {
22             for(int p = 0;p <= j;p++)
23             {
24                 if(p-2 >= 0)
25                 {
26                     dp[u][j][1] = max(dp[u][j][1],dp[u][j-p][1]+dp[v][p-2][1]);
27                 }
28                 if(p-1 >= 0)
29                 {
30                     dp[u][j][0] = max(dp[u][j][0],dp[u][j-p][1]+dp[v][p-1][0]);
31                 }
32                 if(p-2 >= 0)
33                 {
34                     dp[u][j][0] = max(dp[u][j][0],dp[u][j-p][0]+dp[v][p-2][1]);
35                 }
36             }
37         }
38     }
39 }
40 int main()
41 {
42     memset(dp,0,sizeof(dp));
43     cin >> n >> k;
44     for(int i = 1;i <= n;i++)
45     {
46         scanf("%d",&val[i]);
47     }
48     for(int i = 1;i < n;++i)
49     {
50         int u,v;
51         scanf("%d%d",&u,&v);
52         vec[u].push_back(v);
53         vec[v].push_back(u);
54     }
55     for(int i = 1;i <= n;i++)
56     {
57         for(int j = 0;j <= k;j++)
58         {
59             dp[i][j][0] = dp[i][j][1] = val[i];
60         }
61     }
62     dfs(1,1);
63     cout << max(dp[1][k][0],dp[1][k][1]) << endl;
64     return 0;
65 }

输出

复制