POJ 1155 TELE

正文索引 [隐藏]

传送门:http://vjudge.net/problem/16417

题目大意

一个以 根节点 为根的树,每个叶子节点有收益,每条边有花费。求在不亏本的时候,最多能使多少叶子节点与 根节点 联通。

题解

树形DP
先多叉转二叉(左兄弟右孩子),然后在二叉树上DP。F[i][k]表示以 i 为根的节点,去 k 个叶子节点的最大收益。

代码