关键词：

样例1输入
3 5
9 2 5
1 2
1 3

样例2输入
4 5
1 1 1 2
1 2
2 3
3 4

样例3输入
5 10
1 3 5 2 4
5 2
3 1
2 3
4 2
 

样例1输出
14

样例2输出
3

样例3输出
15
 

题解

• 设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 

hdu1561themore,thebetter(树形dp)(代码片段)

Themore,TheBetterTimeLimit:6000/2000MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):9938    AcceptedSubmission(s):5788ProblemDescript 查看详情

[树形dp][组合数]jzojp1794保镖排队

Description【问题背景】　　教主LHX作为知名人物，时刻会有恐怖分子威胁他的生命。于是教主雇佣了一些保镖来保障他的人生安全。【题目描述】　　教主一共雇佣了N个保镖，编号为1~N。每个保镖虽然身手敏捷武功高强，但是他... 查看详情

[树形dp]jzojp3914人品问题(代码片段)

Description网上出现了一种高科技产品——人品测试器。只要你把你的真实姓名输入进去，系统将自动输出你的人品指数。yzx不相信自己的人品为0。经过了许多研究后，yzx得出了一个更为科学的人品计算方法。这种方法的理... 查看详情

[dp]jzojp5804简单的序列(代码片段)

Description从前有个括号序列s，满足|s|=m。你需要统计括号序列对(p,q)的数量。其中(p,q)满足|p|+|s|+|q|=n，且p+s+q是一个合法的括号序列。 Input从文件bracket.in 中读入数据。第一行两个正整数n,m。第二行一个长度为m的括号序列... 查看详情

[容斥原理][dp]jzojp3056数字(代码片段)

【问题描述】    一个数字被称为好数字当他满足下列条件：1. 它有2*n个数位，n是正整数(允许有前导0)   2. 构成它的每个数字都在给定的数字集合S中。   3. 它前n位之和与后n位之... 查看详情

bailian4118开餐馆dp(代码片段)

4118:开餐馆总时间限制:1000ms内存限制:65536kB描述北大信息学院的同学小明毕业之后打算创业开餐馆.现在共有n个地点可供选择。小明打算从中选择合适的位置开设一些餐馆。这n个地点排列在同一条直线上。我们用一个整数序列m1,m... 查看详情

[dp总结]树形dp(代码片段)

树形DP树形DP，顾名思义，是在树上进行DP操作，因此往往需要使用DP实现，在转移时，通常先递归求出子树中的解，再在根节点进行计算转移。树中只有两种关系，一种是父子关系，一种是平行关系。下面是几道简单的树形DP。... 查看详情

树形dp进阶(代码片段)

树形DP进阶P2899[USACO08JAN]CellPhoneNetworkG考虑结点被谁染色，显然三种情况：自己、父亲、儿子。然后就是裸的树形dpdpdp了。难点在于求dp[u][0]dp[u][0]dp[u][0]，即被儿子染色的情况。我们只需枚举那个儿子被染色即可。voiddf... 查看详情

树形dp入门(代码片段)

今天学了树形dp，发现树形dp就是入门难一些，于是好心的我便立志要发一篇树形dp入门的博客了。树形dp的概念什么的，相信大家都已经明白，这里就不再多说。直接上例题。一、常规树形DPP1352没有上司的舞会题目描述某大学有... 查看详情

anniversaryparty(树形dp入门)(代码片段)

Anniversaryparty HDU-1520 Thereisgoingtobeapartytocelebratethe80-thAnniversaryoftheUralStateUniversity.TheUniversityhasahierarchicalstructureofemployees.Itmeansthatthesupervisorrelationforms 查看详情

uva12186：anothercrisis（树形dp）(代码片段)

一道简单的树形DP送给你。 Acoupleofyearsago,anewworldwidecrisisstarted,leavingmanypeoplewitheconomicalproblems.Someworkersofaparticularcompanyaretryingtoaskforanincreaseintheirsalaries.数年以前，人们遭受了世界范围的经济危机。于是 查看详情

树形dp(代码片段)

一、P2656采蘑菇#include<cstring>#include<cstdio>#include<algorithm>#include<iostream>#include<cmath>usingnamespacestd;#definemaxn80010#definemaxm300010structEdgeintu,v,w,next 查看详情

树形dp入门(代码片段)

一、基本概念    树形DP，即在树上进行DP。一般都用递归的形式进行实现，根据叶子节点的信息对根节点进行DP。二、经典问题    1、树的重心       重心的定义：若删去树... 查看详情

[计数dp][数学]jzojp4254集体照(代码片段)

Description   一年一度的高考结束了，我校要拍集体照。本届毕业生共分n个班，每个班的人数为Ai。这次拍集体照的要求非常奇怪：所有学生站一排，且相邻两个学生不能同班。现在，安排这次集体照的老师找到了你，... 查看详情

averagedistance(类树形dp)(代码片段)

Averagedistance HDU-2376 Givenatree,calculatetheaveragedistancebetweentwoverticesinthetree.Forexample,theaveragedistancebetweentwoverticesinthefollowingtreeis(d 01 +d 02  查看详情

poj1463(简单树形dp)(代码片段)

StrategicgameTimeLimit:2000MS MemoryLimit:10000KTotalSubmissions:9313 Accepted:4368DescriptionBobenjoysplayingcomputergames,especiallystrategicgames,butsometimeshecannotfindthesolutionfasten 查看详情

[dp]jzojp6012荷马史诗(代码片段)

Description    追逐影子的人，自己就是shadow。——荷马    Shadow最近迷上了文学。她喜欢在一个慵懒的午后，细细地品上一杯卡布奇诺，静静地阅读她爱不释手的《荷马史诗》。但是由《奥德赛... 查看详情

dp树形dp(代码片段)

题单( exttt毛毛虫)对于这种题目，我们可以先算出以(u)为头的毛毛虫，然后再算趴在节点(u)上的毛毛虫。题解( extttPOI-Farmcraft)由于题目的设定我们可以发现，一个子树一旦进去就必须走完这个子树的所有点才能出来，所以肯定设... 查看详情