#agc009d. [agc009_d]Uninity
[agc009_d]Uninity
题目描述
我们递归地定义树的“统一性”如下:(“Uni”是日语中海胆的意思。)
- 仅包含一个顶点的树的统一性为 。
- 假设有 个统一性为 的树以及一个顶点 。如果从每棵树中选择一个顶点并用边连接到 ,则得到的树的统一性为 。
可以证明,统一性为 的树也是统一性为 的树,依此类推。
给定一棵由 个顶点组成的树。树的顶点编号为 到 ,第 条边连接顶点 和 。
找出使得给定的树具有统一性 的最小值。
约束条件
- 给定的图是一棵树。
输入
输入以以下格式从标准输入给出:
:
输出
打印使得给定的树具有统一性 的最小值。
示例 1
输出 1
可以通过以下方式构造包含顶点 、、 和 的统一性为 的树:顶点 构成的统一性为 的树,顶点 构成的统一性为 的树,顶点 构成的统一性为 的树和顶点 。
可以通过以下方式构造包含顶点 和 的统一性为 的树:顶点 构成的统一性为 的树和顶点 。
可以通过以下方式构造包含顶点 、、、、、 和 的统一性为 的树:顶点 、、 和 构成的统一性为 的树,顶点 和 构成的统一性为 的树以及顶点 。