题目理解

题意：
给一棵 $n$ 个结点的树（无向边）。
我们想把每条无向边定向（变成有向边），这样就能得到一些“好的”有序对 $(u,v)$，表示 $u$ 可以沿着有向边走到 $v$。

定义：

• 如果 $u$ 到 $v$ 之间有一条有向路径，那么 $(u,v)$ 是“好”的。
• 初始时，每条边定向后，至少会给出两个方向中的一个（因为一条边只能定一个方向，所以 $n-1$ 条边至少给 $n-1$ 个好对——注意这里每个有序对是一个方向）。
• 题目要求：恰好有 $n$ 个好对。

---

关键推导

1. 最少好对数

在树中，每条边定向后，恰好产生一个方向的好对（比如 $(u,v)$ 或 $(v,u)$），所以至少 $n-1$ 个好对。

我们需要多一个好对，即总共有 $n$ 个好对。

---

2. 好对的长度分析

• 长度 $1$ 的好对正好就是定向后的边（有向边）。
• 所以要想多一个好对，必须有一个长度至少为 $2$ 的路径（比如 $u \to r \to v$）。
• 如果路径长度大于 $2$（比如 $u \to r \to v \to w$），那么它的子路径（比如 $u \to v$ 或 $r \to w$）也会成为好对，这样就会超过 $n$ 个。

因此，唯一可能的结构是：
只有所有有向边（长度1）和一个长度为 2 的路径 $u \to r \to v$。

---

3. 中间点 $r$ 的限制

考虑长度为 2 的路径的中间点 $r$。
如果 $r$ 还有另一个邻居 $t$（不同于 $u$ 和 $v$），那么：

• 如果 $t \to r$，那么 $t \to r \to v$ 是长度为 2 的好对，多了一个。
• 如果 $r \to t$，那么 $u \to r \to t$ 是长度为 2 的好对，多了一个。

不管怎样，都会产生第二个长度为 2 的好对，加上原来的那个就变成 $n+1$ 个好对了（因为原来的长度1有 $n-1$ 个，加上两个长度2，一共 $n+1$）。
所以 $r$ 的度数必须恰好为 2。

---

4. 结论

• 原树中必须有一个度数为 2 的点 $r$，否则无解。
• 如果有，就可以构造。

---

构造方法

1. 找到度数为 2 的点 $r$。设它的两个邻点为 $a$ 和 $b$。
2. 定向：
   • $a \to r$
   • $r \to b$
3. 从 $a$ 出发：所有其它边都从 $a$ 指向外（即 $a \to x$ 对于 $x \neq r$）。
4. 向 $b$ 汇聚：所有其它边都指向 $b$（即 $y \to b$ 对于 $y \neq r$）。
5. 递归处理：
   • 对于 $a$ 的其它邻居 $x$，它们作为新的“起点”，向外指（相对于它们的父边）? 其实在实现中，是 dfs 交替方向。

---

为什么不会产生额外好对？

因为除了 $a \to r \to b$ 这条长度 2 的路径，任何其他路径要么起点出度大但只能走到 $a$ 方向，要么终点入度大但只能从 $b$ 方向进入，不会形成第二个长度 2 的好对。

---

代码实现

输入与建图

int n;
vector<int> g[N];

• 邻接表存树。

找度数为 2 的点

int r = 0;
while (r < n && sz(g[r]) != 2) r++;
if (r >= n) { cout << "NO\n"; return; }

• 如果不存在度数为 2 的点，输出 NO。

定向

ans.emplace_back(r, g[r][0]);  // r -> a
ans.emplace_back(g[r][1], r);  // b -> r

• $r$ 的两个邻居：$g[r][0]$（记为 $a$），$g[r][1]$（记为 $b$）。

DFS 构造

void dfs(int v, bool in) {
    used[v] = 1;
    for (int to : g[v]) {
        if (used[to]) continue;
        if (in) ans.emplace_back(to, v);  // to -> v (汇聚)
        else   ans.emplace_back(v, to);   // v -> to (外指)
        dfs(to, !in);
    }
}

• 从 $a$ 出发，用 in = true，意思是 $a$ 的邻居要指向 $a$（汇聚方向）。
• 从 $b$ 出发，用 in = false，意思是 $b$ 的邻居要从 $b$ 向外指。

为什么这样交替？
因为我们要保证除了 $a \to r \to b$ 外，其他路径都不会有长度 2 的好对。
这个 DFS 模式实际是在树的两个分支上做“远离 r 的方向”，并交替方向，从而不会产生新的 $x \to y \to z$ 路径。

---

输出

cout << "YES\n";
sort(ans.begin(), ans.end());
for (auto [u, v] : ans)
    cout << u+1 << " " << v+1 << '\n';

• 排序是为了输出稳定，无顺序要求可省略。

---

总结

• 必要条件：存在度数为 2 的点。
• 构造方法：以该点为中间点，把树分成两半，一边向外指，一边向内指。
• 时间复杂度：$O(n)$。