被感染的树

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

给定一棵以顶点 $1$ 为根的二叉树。这里二叉树按无向图给出：根的度数不超过 $2$，其他顶点的 度数不超过 $3$。初始时只有根节点被感染。

接下来进行 $n$ 轮操作。每一轮中，你可以删除一个尚未感染且未被删除的顶点以及与它相连的所有边， 也可以什么都不做；随后感染会从所有已感染顶点传播到与其直接相邻、尚未删除的顶点。

最终未被感染且未被删除的顶点视为获救。求最多能拯救多少个顶点。

输入格式

第一行包含一个整数 $t$，表示测试用例数量。

每个测试用例的第一行包含一个整数 $n$。接下来 $n-1$ 行每行包含两个整数 $u,v$，表示一条树边。

输出格式

对每个测试用例输出一行一个整数，表示最多能拯救的顶点数。

样例输入 1

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

样例输出 1

0
2
2
10

数据范围

$1\le t\le5000$，$2\le n\le3\cdot10^5$；保证每组输入是以 $1$ 为根的二叉树， 且所有测试用例的 $n$ 之和不超过 $3\cdot10^5$。