题目描述

给出一棵含 $n$ 个结点的树，求它的一个最小路径覆盖。路径覆盖是指将点集划分为若干点不相交的路径的方案。

输入格式

本题有多组数据，第一行包含一个正整数 $t$ ($1 \le t \le 10$)，表示数据组数，下面共描述了 $t$ 组数据。

对于每组数据，第一行包含一个整数 $n$ ($1 \le n \le 10^4$)。接下来 $n - 1$ 行，每行包含两个正整数 $(u_i, v_i)$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$)，表示结点 $u_i$ 和结点 $v_i$ 相连。

输出格式

对于每组数据，打印一行，包含一个整数，表示最小路径覆盖数。

1
7
1 2
2 3
2 4
4 6
5 6
6 7

3

数据范围与提示

对于样例中的树，$\{(1,2,3), (4), (5,6,7)\}$ 就是它的一个最小路径覆盖。而 $\{(1,2,3,4,5), (3), (7)\}$ 也是它的最小路径覆盖。注意此注释有误，第二种情况应该为$\{1,2,4,5,6\},\{3\},\{7\}$

题目来源

Play with Tree By Amber