CF1943C.Tree Compass

给定一棵有 $n$ 个顶点的树，顶点编号为 $1, 2, \ldots, n$。初始时，所有顶点均为白色。

你可以进行如下两步操作：

1. 选择一个顶点 $v$（$1 \leq v \leq n$）和一个距离 $d$（$0 \leq d \leq n-1$）。
2. 对所有满足 $\text{dist}^\dagger(u,v)=d$ 的顶点 $u$（$1 \leq u \leq n$），将其染成黑色。

请构造一组操作序列，使得用最少的操作次数将树中所有节点都染成黑色。可以证明，最多只需 $n$ 次操作一定可以完成。

$^\dagger$ 其中 $\text{dist}(x, y)$ 表示树上顶点 $x$ 和 $y$ 之间唯一简单路径上的边数。

每个测试点包含多组测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 200$），表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^3$），表示树的顶点数。

接下来的 $n-1$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$，$u_i \neq v_i$），表示树中的一条边连接了顶点 $u_i$ 和 $v_i$。

保证给定的边构成一棵树。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^3$。

对于每个测试用例，首先输出一个整数 $op$（$1 \le op \le n$），表示染黑所有顶点所需的最小操作次数。

接下来输出 $op$ 行，每行包含两个整数，分别表示第 $i$ 次操作选择的 $v$ 和 $d$（$1 \le v \le n$，$0 \le d \le n-1$）。

你需要保证在 $op$ 次操作后，所有顶点都被染成黑色。

如果有多种方案，可以输出任意一种。

在第一个测试用例中，只有一种可能的操作，执行后即可得到一个合法答案。

在第二个测试用例中，第一次操作将顶点 $2$ 染黑，第二次操作将顶点 $1$ 染黑。可以证明无法通过一次操作将两个顶点都染黑，因此最少需要 $2$ 次操作。另一种可行方案是两次操作分别为 $(u, r) = (1, 0)$ 和 $(u, r) = (2, 0)$。

在第三个测试用例中，第一次操作将顶点 $2$、$3$ 和 $4$ 染黑，第二次操作将顶点 $1$ 染黑。同样可以证明无法在一次操作内将所有顶点染黑，因此最少需要 $2$ 次操作。

在第四个测试用例中，第一次操作将顶点 $4$、$1$ 和 $7$ 染黑，第二次操作将顶点 $2$、$5$ 和 $6$ 染黑，第三次操作将顶点 $3$ 和 $7$ 染黑。注意顶点 $7$ 被染黑了两次。

因此，每个节点至少被染黑一次，其中顶点 $7$ 被染黑了两次。可以证明无法用少于 $3$ 次操作将所有顶点染黑。

由 ChatGPT 4.1 翻译