3706. [CF1689C]Infected Tree

【题目描述】

给定一棵以 $1$ 号节点为根的二叉树，总节点个数为 $n$。

现在 $1$ 号节点感染了病毒，病毒每一回合都会去感染与该节点直接相连的节点，而你在这一回合里可以选择删除任意一个没有被病毒感染（尚未被删除）的点，这样就断开了它与其直接相连的点得关系。

询问最多可以有多少不被病毒感染的点，被删除的点不算做不被病毒感染的点。

【输入格式】

第一行一个整数 $T$，表示数据组数。

每组数据中，第一行一个整数 $n$，表示节点个数。

下面 $n-1$ 行，每行两个整数 $u,v$，表示 $(u,v)$ 间有一条边。

【输出格式】

一个整数，表示最多不被感染的点的数量。

【样例输入】

4
2
1 2
4
1 2
2 3
2 4
7
1 2
1 5
2 3
2 4
5 6
5 7
15
1 2
2 3
3 4
4 5
4 6
3 7
2 8
1 9
9 10
9 11
10 12
10 13
11 14
11 15

【样例输出】

0
2
2
10

【样例说明】

在第二组数据中，通过删除点 $2$ 保住点 $3,4$。

【数据规模与约定】

$1 \le T \le 5000,1 \le \sum n \le 3 \times 10^5$。

【来源】

CF1689C