Tree Matching

题目描述

给定一棵包含 $n$ 个节点的树。 匹配是一些边的集合，使得每个节点至多是其中一条边的端点。匹配中最多可以有多少条边？

输入格式

第一行输入包含一个整数 $n$：节点数。节点编号为 $1,2,\ldots,n$。 接下来有 $n-1$ 行描述边。每行包含两个整数 $a$ 和 $b$：在节点 $a$ 和 $b$ 之间有一条边。

输出格式

输出一个整数：最多的配对数。

5
1 2
1 3
3 4
3 5

2

提示

$1 \le n \le 2 \cdot 10^5$ $1 \le a,b \le n$ 样例解释：一种可能的匹配是 $(1,2)$ 和 $(3,4)$。

标签: CSES1130|树

来源

CSES1130|树