H. 树的匹配

Type: Default

1000ms

256MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

翻译自 CSES-1130 题。

给定一个包含 $n$ 个节点的树。

匹配是一个边的集合，其中每个节点最多是一个边的端点。你需要计算在树中能找到的最大匹配数。

第一行包含一个整数 $n$ ：表示节点的数量，节点编号为 $1,2,…,n$ 。

接下来的 $n−1$ 行，每行包含两个整数 $a$ 和 $b$ ：表示节点 $a$ 和节点 $b$ 之间有一条边。

输出一个整数：表示最大匹配数，即最大可以选取的匹配边数。

一个可能的匹配是： $(1,2)$ 和 $(3,4)$ 。

$1 \leq n \leq 2 \cdot 10^5$ ；

$1 \leq a ,b \leq n$ 。