CF1689C Infected Tree

Byteland 是一个以美丽的树木闻名的美丽国度。 Misha 发现了一棵有 $n$ 个顶点的二叉树，顶点编号从 $1$ 到 $n$。二叉树是一个包含 $n$ 个顶点和 $n-1$ 条边的无环连通无向图。每个顶点的度数最多为 $3$，其中根节点编号为 $1$，其度数最多为 $2$。 不幸的是，根节点被感染了。 接下来会进行 $n$ 次如下操作： - Misha 可以选择一个未被感染（且未被删除）的顶点，将其与所有连接到该顶点的边一起删除，或者什么都不做。 - 然后，感染会传播到所有与已感染顶点通过一条边相连的顶点（所有已感染的顶点仍然保持感染状态）。 由于 Misha 没有太多时间思考，请你告诉他最多能拯救多少个顶点不被感染（注意，被删除的顶点不计入被拯救的顶点）。

输入包含若干组测试数据。第一行包含一个整数 $t$（$1\leq t\leq 5000$），表示测试用例的数量。接下来是每组测试数据的描述。 每组测试数据的第一行包含一个整数 $n$（$2\leq n\leq 3\cdot 10^5$），表示树的顶点数。 接下来的 $n-1$ 行中，第 $i$ 行包含两个正整数 $u_i$ 和 $v_i$（$1\leq u_i, v_i\leq n$），表示图中存在一条连接 $u_i$ 和 $v_i$ 的边。 保证给定的图是一棵以 $1$ 为根的二叉树。保证所有测试用例中 $n$ 的总和不超过 $3\cdot 10^5$。

对于每个测试用例，输出 Misha 最多可以拯救多少个顶点。

在第一个测试用例中，唯一可能的操作是删除顶点 $2$，此时总共可以拯救 $0$ 个顶点。 在第二个测试用例中，如果删除顶点 $2$，可以拯救顶点 $3$ 和 $4$。  由 ChatGPT 4.1 翻译