poj 3107 Godfather（树形dp）

本文出自 http://blog.csdn.net/shuangde800

--------------------------------------------------------------------------------------

题目链接： poj-3107

题意

给一颗n个结点的树，节点编号为1~n，问删除一个节点之后，让剩下的分支中节点数量最多的尽量少。
可能有多种方案，按编号顺序输出。

思路

简单的树形dp. 其实连dp都不能算吧...就是直接计数统计
先dfs计算每个节点子树的节点个数tot[i]。
再次dfs更新答案：
f[i] = max( n-tot[i], max{tot[v] | v是i的儿子} );
两个dfs可以合并在一个dfs里完成, 复杂度O(n)

代码

<script src="https://code.csdn.net/snippets/777.js" type="text/javascript"></script>