CF2112D Reachability and Tree
link
题意
给定一棵 \(n\) 个点的树，求一种为边定向的方案使得树上能两两到达的点恰好有 \(n\) 对。多测。\(\sum n\leq 2\times 10^5\)。
题解
先手玩样例，发现只要一正一反定向就会出现 \(n-1\) 对，因为每一条边至少都有 \(1\) 对。继续观察发现一条长度为 \(m\) 的链上答案是 \(m(m-1)\over 2\)。那还需要再多一对，即需要一条长度为 \(2\) 的链。具体做法是原树上度为 \(2\) 的点的子树边的方向全部取反，这样该点和其父亲就会形成链。当然，如果是根就特判一下，把根变成其他的点。复杂度 \(O(n)\)。aclink。
坑
- 如果 \(1\) 是那个点需要把根变成其他点，因为根没有父亲，也就不能形成链。
代码
#include<bits/stdc++.h>
#define i64 long long
#define L(a,b,c,d) for(int a=b;a<=c;a+=d)
#define R(a,b,c,d) for(int a=b;a>=c;a-=d)using namespace std;
const int N=2e5+5;void solve();
int n,k;
vector<int> a[N];signed main(){int Test=1;scanf("%d",&Test);while(Test--) solve();return 0;
}void dfs(int u,int last,bool f){if(u==k){f=!f;}for(auto v:a[u]){if(v!=last){if(f) printf("%d %d\n",u,v);else printf("%d %d\n",v,u);dfs(v,u,!f);}}
}void solve(){scanf("%d",&n);L(i,1,n,1) a[i].clear();L(i,1,n-1,1){int x,y;scanf("%d%d",&x,&y);a[x].push_back(y);a[y].push_back(x);}k=-1;L(i,1,n,1){if(a[i].size()==2){k=i;break;}}if(k==-1){printf("No\n");return;}printf("Yes\n");if(k==1) dfs(2,-1,1);else dfs(1,-1,1);
}