5211. 树的匹配（Tree Matching）
时间限制：1000 MS 内存限制：512 MB
题目描述
## 题目描述 你得到了一棵由 $n$ 个节点组成的树。 一个**匹配（matching）**是一组边的集合，其中每个节点最多是一个边的端点。换句话说，任意两条边在匹配中不能共享一个节点。 你的任务是找出这棵树中可以选出的**最大匹配边数** —— 即：**在这棵树中选择尽可能多的边，使得没有两个边共享同一个节点**。 ## 输入格式 第一行包含一个整数 $n$：表示树中节点的数量。 节点编号为 $1, 2, \dots, n$。 接下来有 $n-1$ 行，每行包含两个整数 $a$ 和 $b$：表示节点 $a$ 和 $b$ 之间有一条边。 ## 输出格式 输出一个整数：这棵树的最大匹配边数。 ## 输入输出样例 ### 输入 #1 ``` 5 1 2 1 3 3 4 3 5 ``` ### 输出 #1 ``` 2 ``` ## 说明/提示 ### 样例解释 一种可能的匹配方式是选择边 $(1,2)$ 和 $(3,4)$，这两个边没有共享任何相同的节点。 ### 数据规模与约定 - $1 \le n \le 2 \times 10^5$ - $1 \le a, b \le n$