A15103. Infected Tree
编程题
普及/提高-
知识点
题目描述
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).
拜特兰是一片美丽的土地，因其美丽的树木而闻名。
米沙发现了一棵二叉树，它有 $n$ 个顶点，编号从 $1$ 到 $n$ 。二叉树是一个非循环连接的双向图，包含 $n$ 个顶点和 $n - 1$ 条边。每个顶点的度最多为 $3$ ，而根是编号为 $1$ 的顶点，它的度最多为 $2$ 。
不幸的是，根节点被感染了。
下面的过程会发生 $n$ 次：
- 米莎要么选择一个未感染(也未删除)的顶点，删除它和所有以该顶点为终点的边，要么什么也不做。
- 然后，感染会扩散到与已感染顶点有边相连的每个顶点(所有已感染顶点都会继续受到感染)。
由于 Misha 没有太多时间思考，请告诉他最多可以从感染中挽救多少个顶点(注意，删除的顶点不计入挽救的顶点)。
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).
拜特兰是一片美丽的土地，因其美丽的树木而闻名。
米沙发现了一棵二叉树，它有 $n$ 个顶点，编号从 $1$ 到 $n$ 。二叉树是一个非循环连接的双向图，包含 $n$ 个顶点和 $n - 1$ 条边。每个顶点的度最多为 $3$ ，而根是编号为 $1$ 的顶点，它的度最多为 $2$ 。
不幸的是，根节点被感染了。
下面的过程会发生 $n$ 次：
- 米莎要么选择一个未感染(也未删除)的顶点，删除它和所有以该顶点为终点的边，要么什么也不做。
- 然后，感染会扩散到与已感染顶点有边相连的每个顶点(所有已感染顶点都会继续受到感染)。
由于 Misha 没有太多时间思考，请告诉他最多可以从感染中挽救多少个顶点(注意，删除的顶点不计入挽救的顶点)。
输入格式
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$ .
输入
输入数据中有多个测试用例。第一行包含一个整数 $t$ ( $1\leq t\leq 5000$ )--测试用例数。随后是测试用例说明。
每个测试用例的第一行包含一个整数 $n$ ( $2\leq n\leq 3\cdot 10^5$ ) - 树的顶点数。
测试用例中下面 $n-1$ 行的 $i$ -th 包含两个正整数 $u_i$ 和 $v_i$ . $1 \leq u_i, v_i \leq n$ ），这意味着在图中它们之间存在一条边。
保证该图是一棵根植于 $1$ 的二叉树。同时保证所有测试用例中 $n$ 的总和不会超过 $3\cdot 10^5$ 。
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$ .
输入
输入数据中有多个测试用例。第一行包含一个整数 $t$ ( $1\leq t\leq 5000$ )--测试用例数。随后是测试用例说明。
每个测试用例的第一行包含一个整数 $n$ ( $2\leq n\leq 3\cdot 10^5$ ) - 树的顶点数。
测试用例中下面 $n-1$ 行的 $i$ -th 包含两个正整数 $u_i$ 和 $v_i$ . $1 \leq u_i, v_i \leq n$ ），这意味着在图中它们之间存在一条边。
保证该图是一棵根植于 $1$ 的二叉树。同时保证所有测试用例中 $n$ 的总和不会超过 $3\cdot 10^5$ 。
输出格式
For each test case, output the maximum number of vertices Misha can save.
输出
针对每个测试案例，输出 Misha 能保存的最大顶点数。
输出
针对每个测试案例，输出 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
说明/提示
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$ .
备注
在第一个测试案例中，唯一可能的操作是删除顶点 $2$ ，之后我们总共保存了 $0$ 个顶点。
在第二个测试案例中，如果删除顶点 $2$ ，我们可以保存顶点 $3$ 和 $4$ 。
In the second test case, if we delete vertex $2$ , we can save vertices $3$ and $4$ .
备注
在第一个测试案例中，唯一可能的操作是删除顶点 $2$ ，之后我们总共保存了 $0$ 个顶点。
在第二个测试案例中，如果删除顶点 $2$ ，我们可以保存顶点 $3$ 和 $4$ 。