 D. Reachability and Tree R1700)
题意：给定一个含有n个点的树，现在要求选择改变所有边的方向，使得：对于1-n的每个点，它们各自能够通过边到达的其他点的个数的和恰好为n。
思路：
1.首先，num == n这个条件非常苛刻：因为一条边无论是什么方向，它对总个数的贡献至少为1，也就是说，num至少为n - 1。
2.先考虑什么情况下可以达到 num = n - 1 : 当边方向交替的时候便可以。 如 1 -> 2 <- 3
3.那么什么情况下，怎么改变其中一条边的方向，可以让num恰好+1呢？其实不难发现：把交替方向的 1->2-<3改成 1->2->3即可。
4.然后注意到，貌似当deg[i] > 2的时候，就无法对一个部分改变其中一条边的方向，使得它对num的贡献恰好+1了。
5.于是寻找一个deg == 2的点，开始dfs构造边，当遇到k的时候就翻转方向。
细节：我们选取dfs的开始点为g[k][0],避免从K开始导致k被跳过处理了。
code:
#include<bits/stdc++.h>
using namespace std;
#define maxn 200005
vector<int> g[maxn];
int deg[maxn];
int k = -1;void dfs(int p, int fa, bool op) {if (p == k) op = !op;for (int x : g[p]) {if (x != fa) {if (op) cout<<p<<" "<<x<<endl;else cout<<x<<" "<<p<<endl;dfs(x, p, !op);}}
}void solve() {int n; cin>>n;for (int i = 0; i <= n; ++i) {g[i].clear();deg[i] = 0;}for (int i = 0; i < n - 1; i++) {int u, v; cin>>u>>v;deg[u]++;deg[v]++;g[u].push_back(v);g[v].push_back(u);}k = -1;for (int i = 1; i <= n; ++i) {if (deg[i] == 2) {k = i;break;}}if (k == -1) {cout<<"NO"<<endl;return;}cout<<"YES"<<endl;int s = g[k][0];dfs(s, s, 1);return;
}int main() {int tt; cin>>tt;while (tt--) solve();
}