题目描述

给出一棵含 $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} \neq v_ {i} )$，表示结点 $u_ {i}$ 和结点 $v_ {i}$ 相连。

输出格式

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

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

3

题目来源

Play with Tree By Amber