CF1830A Copil Copac Draws Trees

Copil Copac 得到了一棵有 $n$ 个顶点的树的 $n-1$ 条边的列表。他决定用如下算法绘制这棵树： - 第 $0$ 步：画出第一个顶点（顶点 $1$）。进入第 $1$ 步。 - 第 $1$ 步：对于输入中的每一条边，按顺序：如果这条边连接了一个已经画出的顶点 $u$ 和一个未画出的顶点 $v$，他就画出未画出的顶点 $v$ 以及这条边。检查完所有边后，进入第 $2$ 步。 - 第 $2$ 步：如果所有顶点都已画出，算法终止。否则，回到第 $1$ 步。 “读边次数”定义为 Copil Copac 执行第 $1$ 步的次数。 请你求出 Copil Copac 绘制这棵树所需的读边次数。

每个测试点包含多个测试用例。输入的第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$），表示树的顶点数。 接下来的 $n-1$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$，$u_i \neq v_i$），表示第 $i$ 条边连接 $u_i$ 和 $v_i$。保证给出的边集构成一棵树。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出 Copil Copac 绘制这棵树所需的读边次数。

在第一个测试用例中： 第一次读边后，树的样子如下：  第二次读边后：  因此，Copil Copac 需要 $2$ 次读边才能画出这棵树。 由 ChatGPT 4.1 翻译