HDU 5834 Magic boy Bi Luo with his excited tree

正文索引 [隐藏]

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=5834

题目翻译

有一颗有N个节点的树,经过节点i得到V[i]点(只能得到一次),经过边i消耗C[i]点(可以重复消耗),问每个点可以获得的最大点数是多少。

题解

树DP
首先我们假装之询问点1。
我们记F[i]表示以i为根的子树从i出发不需要返回所能获得的最大点数,FB[i]表示以i为根的子树从i点出发一定要返回到i点所能获得的最大点数,Cost(i,j)表示i,j之间的花费
很明显,点i的FB[i]是其所有儿子j FB[j]-Cost(i,j) 不小于零的和
即FB[i]=V[i] + sum( max( 0 , FB[j] + 2Cost(i,j) ) ) j为i的儿子
点i的F[i],就是在FB[i]的基础上把一条需要返回的边给去掉,的最大值。
F[i]=FB[i]-Cost(i,j)+F[V]-max( 0 , FB[j] + 2
Cost(i,j) ) j为i的儿子
这样树DP就能求得点1的答案
然后我们关注所有点,我们发现对于一个已经算过的点i,我们求得与其相邻的点j的答案,只需要在点i已经算好的基础上,把根当成j重算点i,j的答案。
如此不停的移动根就可以算出所有的答案了。
Tip,重算的时候,我们不可以重新遍历点的每一个儿子,这样会被菊花图卡成O(N^2)的,所以我们需要记录一下已经算过的东西,降低移动根的代价。

代码