Infected Tree

题意翻译

给定一棵以$1$ 号节点为根的二叉树，总节点个数为 $n$。 现在 $1$ 号节点感染了病毒，病毒每一回合都会去感染与该节点直接相连的节点，而你在这一回合里可以选择删除任意一个没有被病毒感染（尚未被删除）的点，这样就断开了它与其直接相连的点得关系. 询问最多可以有多少不被病毒感染的点，被删除的点不算做不被病毒感染的点

题目描述

Byteland is a beautiful land known because of its beautiful trees. Misha has found a binary tree with $ n $ vertices, numbered from $ 1 $ to $ n $ . A binary tree is an acyclic connected bidirectional graph containing $ n $ vertices and $ n - 1 $ edges. Each vertex has a degree at most $ 3 $ , whereas the root is the vertex with the number $ 1 $ and it has a degree at most $ 2 $ . Unfortunately, the root got infected. The following process happens $ n $ times: - Misha either chooses a non-infected (and not deleted) vertex and deletes it with all edges which have an end in this vertex or just does nothing. - Then, the infection spreads to each vertex that is connected by an edge to an already infected vertex (all already infected vertices remain infected). As Misha does not have much time to think, please tell him what is the maximum number of vertices he can save from the infection (note that deleted vertices are not counted as saved).

输入输出格式

输入格式

There are several test cases in the input data. The first line contains a single integer $ t $ ( $ 1\leq t\leq 5000 $ ) — the number of test cases. This is followed by the test cases description. The first line of each test case contains one integer $ n $ ( $ 2\leq n\leq 3\cdot 10^5 $ ) — the number of vertices of the tree. The $ i $ -th of the following $ n-1 $ lines in the test case contains two positive integers $ u_i $ and $ v_i $ ( $ 1 \leq u_i, v_i \leq n $ ), meaning that there exists an edge between them in the graph. It is guaranteed that the graph is a binary tree rooted at $ 1 $ . It is also guaranteed that the sum of $ n $ over all test cases won't exceed $ 3\cdot 10^5 $ .

输出格式

For each test case, output the maximum number of vertices Misha can save.

输入输出样例

输入样例 #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

说明

In the first test case, the only possible action is to delete vertex $ 2 $ , after which we save $ 0 $ vertices in total. In the second test case, if we delete vertex $ 2 $ , we can save vertices $ 3 $ and $ 4 $ . 

题目大意：
给定一棵以1号节点为根的二叉树，总节点个数为n。1号节点感染了病毒，病毒每一回合都会感染与已感染节点直接相连的节点，而你可以选择删除任意一个未被感染（且未被删除）的节点，从而断开其与直接相连的节点的关系。求最多可以有多少不被病毒感染的节点，被删除的节点不算作不被病毒感染的节点。

输入输出格式：
输入格式：
- 输入包含多个测试用例。第一行包含一个整数t（1≤t≤5000），表示测试用例的数量。接下来是测试用例的描述。
- 每个测试用例的第一行包含一个整数n（2≤n≤3×10^5），表示树的节点数量。
- 接下来的n-1行，每行包含两个正整数u_i和v_i（1≤u_i,v_i≤n），表示图中存在一条连接它们两个节点的边。
- 保证图是一棵以1为根的二叉树。所有测试用例的n之和不超过3×10^5。

输出格式：
- 对于每个测试用例，输出Misha最多可以拯救的不被病毒感染的节点数量。

输入输出样例：
输入样例 #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
```
说明：
- 在第一个测试用例中，唯一可能的行为是删除节点2，这样总共可以拯救0个节点。
- 在第二个测试用例中，如果删除节点2，可以拯救节点3和节点4。题目大意： 给定一棵以1号节点为根的二叉树，总节点个数为n。1号节点感染了病毒，病毒每一回合都会感染与已感染节点直接相连的节点，而你可以选择删除任意一个未被感染（且未被删除）的节点，从而断开其与直接相连的节点的关系。求最多可以有多少不被病毒感染的节点，被删除的节点不算作不被病毒感染的节点。 输入输出格式： 输入格式： - 输入包含多个测试用例。第一行包含一个整数t（1≤t≤5000），表示测试用例的数量。接下来是测试用例的描述。 - 每个测试用例的第一行包含一个整数n（2≤n≤3×10^5），表示树的节点数量。 - 接下来的n-1行，每行包含两个正整数u_i和v_i（1≤u_i,v_i≤n），表示图中存在一条连接它们两个节点的边。 - 保证图是一棵以1为根的二叉树。所有测试用例的n之和不超过3×10^5。 输出格式： - 对于每个测试用例，输出Misha最多可以拯救的不被病毒感染的节点数量。 输入输出样例： 输入样例 #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 ``` 说明： - 在第一个测试用例中，唯一可能的行为是删除节点2，这样总共可以拯救0个节点。 - 在第二个测试用例中，如果删除节点2，可以拯救节点3和节点4。