题解
- 设f[i][j][0/1]为以i为根的子树中 花费j的时间 是否走回根的最大收益(0为有,1为无)
- 枚举下一棵子树时,可以枚举下一棵子树中所用的时间,和当前子树中用的时间
- 考虑三种转移:
- ①之前走过的子树回根 再走到另一棵子树不回根
- f[i][j][1]=f[i][j-k-1][0]+f[son][k][1]
- ②之前走过的子树回根 再走到另一棵子树也回根
- f[i][j][0]=f[i][j-k-2][0]+f[son][k][0]
- ③走到另一棵子子树回根 之前子树不回根
- f[i][j][1]=f[i][j-k-2][1]+f[son][k][0]
代码
1 #include <cstdio>
2 #include <iostream>
3 #include <cmath>
4 #include <cstring>
5 using namespace std;
6 struct edge { int to,from; }e[510*2];
7 int f[510][510][2],n,m,a[510],head[510],cnt;
8 void insert(int x,int y) { e[++cnt].to=y; e[cnt].from=head[x]; head[x]=cnt; }
9 void dp(int x,int fa)
10 {
11 for (int i=head[x];i;i=e[i].from)
12 {
13 if (e[i].to==fa) continue;
14 dp(e[i].to,x);
15 for (int j=m;j>=1;j--)
16 for (int k=0;k<=m;k++)
17 {
18 if (j-k>=2)
19 f[x][j][1]=max(f[x][j][1],f[x][j-k-2][1]+f[e[i].to][k][0]),
20 f[x][j][0]=max(f[x][j][0],f[x][j-k-2][0]+f[e[i].to][k][0]);
21 if (j-k>=1) f[x][j][1]=max(f[x][j][1],f[x][j-k-1][0]+f[e[i].to][k][1]);
22 }
23 }
24 for (int i=m;i>=1;i--)
25 {
26 f[x][i][0]=max(f[x][i][0],f[x][i-1][0]+a[x]);
27 f[x][i][1]=max(f[x][i][1],f[x][i-1][1]+a[x]);
28 }
29 }
30 int main()
31 {
32 freopen("dostavljac.in","r",stdin);
33 freopen("dostavljac.out","w",stdout);
34 scanf("%d%d",&n,&m);
35 for (int i=1;i<=n;i++) scanf("%d",&a[i]);
36 for (int i=1;i<=n-1;i++)
37 {
38 int u,v;
39 scanf("%d%d",&u,&v);
40 insert(u,v); insert(v,u);
41 }
42 dp(1,0);
43 printf("%d",f[1][m][1]);
44 return 0;
45 }