树形dp____Magic boy Bi Luo with his excited tree( hdu 5834 2
发布时间：2021-01-24 08:37:26 所属栏目：大数据 来源：网络整理
导读：Problem Description Bi Luo is a magic boy,he also has a migic tree,the tree has? N ?nodes,in each node,there is a treasure,it's value is? V [ i ] ,and for each edge,there is a cost? C [ i ] ,which means every time you pass the edge? i ?,yo
|
副标题[/!--empirenews.page--]
Problem Description Bi Luo is a magic boy,he also has a migic tree,the tree has? You may attention that every? Now,Bi Luo define? Bi Luo is also an excited boy,now he wants to know every? Input First line is a positive integer? Four each test： The first line contain an integer? The next line contains? For the next? You can assume that the sum of? Output For the i-th test case,first output Case #i: in a single line,then output? Sample Input 1 5 4 1 7 7 7 1 2 6 1 3 1 2 4 8 3 5 2? Sample Output Case #1: 15 10 14 9 15? 题意： 一个n个节点的数，每个节点有一个价值为pi的宝藏，点之间的边有权值，每次经过该边会扣掉该边权值对应的价值(价值可以为负数继续前行).问分别从每点开始走，最多可以获得多少价值？ 分析： 树形dp。需要讨论的细节比较多。 需要记录两个数据。f[N][2],g[N][2]。以节点1为根节点。 对于f[i][0/1]：f[i][0],表示从i点开始走i - i父亲支路并且回到i点的最大价值，f[i][1] 表示从i开始走i - i父亲支路并且不用回到i点的最大价值。（注意：都不包括i点本身的价值). 对于g[i][0/1]：g[i][0]:表示从i点开始走向子孙节点并且回到i点的最大价值,g[i][1] 表示从i点开始走向子孙节点并且不用回到i点的最大价值。( 注意：都包括i点本身价值). 所以对于任意一点的最大价值为： max( g[i][0]+f[i][1],g[i][1]+f[i][0] ). 至于f,g的状态转移看代码吧。 代码： （编辑：晋中站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
