本文主要是介绍poj1947 Rebuilding Roads，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Description The cows have reconstructed Farmer John’s farm, with its N
barns (1 <= N <= 150, number 1..N) after the terrible earthquake last
May. The cows didn’t have time to rebuild any extra roads, so now
there is exactly one way to get from any given barn to any other barn.
Thus, the farm transportation system can be represented as a tree.Farmer John wants to know how much damage another earthquake could do.
He wants to know the minimum number of roads whose destruction would
isolate a subtree of exactly P (1 <= P <= N) barns from the rest of
the barns.Input
* Line 1: Two integers, N and P
- Lines 2..N: N-1 lines, each with two integers I and J. Node I is node J’s parent in the tree of roads.
Output A single line containing the integer that is the minimum number
of roads that need to be destroyed for a subtree of P nodes to be
isolated.
树形dp，dp[i][j]表示i为根的子树留下j个节点的最小费用。
枚举儿子的时候要不断更新dp[i][j]，dp[i][j]=min{dp[i][j]+1,dp[i][j-k]+dp[son][k]}，前一种表示把子树切掉，后一种不切。初始条件是dp[i][1]=0。
因为答案不一定要留下根，所以要边dfs边更新答案。
这篇关于poj1947 Rebuilding Roads的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
