D. Reachability and Tree

问题描述

设 $u$ 和 $v$ 是有向图中的两个不同顶点。如果存在一条从顶点 $u$ 到顶点 $v$ 的路径，我们称有序对 $(u,v)$ 是好的。

给定一个有 $n$ 个顶点和 $n-1$ 条边的无向树。确定是否可能为这棵树的每条边分配一个方向，使得其中的好对数量恰好为 $n$。如果可能，打印出任何一种能得到恰好 $n$ 个好对的边定向方式。

输入

第一行包含一个整数 $t$ $(1 \leq t \leq 10^4)$ — 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$ $(2 \leq n \leq 2 \cdot 10^5)$ — 树中的顶点数。

接下来的 $n-1$ 行描述了边。第 $i$ 行包含两个整数 $u_i$ 和 $v_i$ $(1 \leq u_i, v_i \leq n; u_i \neq v_i)$ — 由第 $i$ 条边连接的顶点。

保证每个测试用例中的边构成一个无向树，并且所有测试用例的 $n$ 的总和不超过 $2 \cdot 10^5$。

输出

对于每个测试用例，如果不可能给树的所有边定向并获得恰好 $n$ 个好对，则打印 “NO”（不区分大小写）。

否则，打印 “YES”（不区分大小写），然后打印 $n-1$ 对整数 $u_i$ 和 $v_i$，用空格分隔 — 表示从 $u_i$ 到 $v_i$ 的有向边。

边的顺序可以任意。如果存在多个答案，输出任意一个。

题解

思路是找到一个度为2的节点。假设我们有一个度为2的节点 $v$，那么我们可以有 $u \rightarrow v \rightarrow w$。然后让所有其他边的长度为1，我们就会有 $(n-1) + 1 = n$ 个好对。这 $n-1$ 个好对由边提供，另外1个由 $u \rightarrow w$ 提供。

提交链接