CSES1130 树的匹配
#CS1130. 树的匹配
树的匹配
题目背景
翻译自 CSES-1130 题。
题目描述
给定一个包含 n 个节点的树。
匹配是一个边的集合，其中每个节点最多是一个边的端点。你需要计算在树中能找到的最大匹配数。
输入格式
第一行包含一个整数 n：表示节点的数量，节点编号为 1,2,…,n1,2,…,n1,2,…,n。
接下来的 n−1n−1n−1 行，每行包含两个整数 a 和 b：表示节点 a 和节点 b 之间有一条边。
输出格式
输出一个整数：表示最大匹配数，即最大可以选取的匹配边数。
样例
5
1 2
1 3
3 4
3 5
2
样例1解释 一个可能的匹配是：(1,2) 和 (3,4)。
说明/提示