Courses

動態規劃

动态图编程

Module: 动态图编程

Problem

2 /7

最大树匹配

Problem

给定一棵由 n 个顶点组成的树（连通无环无向图）。
找出其最大匹配的大小（成对的不相邻边的集合）。

输入：
第一行包含数字 n - 树中的顶点数。
接下来是 n-1 行，每行包含两个数字 a_i 和 b_i (1 <= a_i, b _i <= n) - 树边。

输出：
打印一个数字——给定树的最大匹配的大小。

示例：
<正文>
解释：
这棵树的最大匹配将包括边 1-2 和 3-4。

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking