题解：CF2112D Reachability and Tree

· · 题解

看起来就在觉得它和 NOI2024 的树的定向（其实我压根儿都没有做过这题）有啥关联，其实一点没有，这是个我上了高一都不会的普及组题。

运用 NOI2024 树的定向特殊性质 A 的思路，对树点黑白染色。每一条边都是指向黑点。就构造出 n-1 的情况了。

设想答案为 n 的情况是把两个距离为 2 的点连接起来。考虑翻转以某一个度数为 2 的节点为根的子树就能达成条件了，否则无解。

要合理选择搜索的根。

#include<bits/stdc++.h>
#define int long long
#define mp(a,b) make_pair(a,b)
using namespace std;

inline int read(){
    int a=0,b=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-')  b=-1;
        c=getchar();
    } 
    while(isdigit(c)){
        a=(a<<1)+(a<<3)+(c-'0');
        c=getchar();
    }
    return a*b;
} 
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>=10)   write(x/10);
    putchar(x%10+48);
}
inline void write1(int x){
    write(x),putchar(' ');
}
inline void write2(int x){
    write(x),putchar('\n');
}
int n;
vector<int> g[5*114514];
int col[5*114514];
int fa[5*114514];
int col1[5*114514];

struct node{
    int x,y;
}edge[5*114514];
int idx;
void dfs(int u){
    if(u==idx)  col1[u]=1;
    for(int i=0;i<g[u].size();i++){
        int v=g[u][i];
        if(fa[u]==v)    continue;
        fa[v]=u;
        col[v]=3-col[u];
        if(col1[u]) col1[v]=1;
        dfs(v);
        if(col1[u]&&col1[v]){
            if(col[u]==1)   write1(u);
            else    write1(v);
            if(col[u]==2)   write2(u);
            else    write2(v);
        }
        else{
            if(col[u]==1)   write1(v);
            else    write1(u);
            if(col[u]==2)   write2(v);
            else    write2(u);
        }
    }
}
void solve(){
//  int n=read();
    n=read();
    for(int i=1;i<n;i++){
        int u=read(),v=read();
        edge[i]=(node){u,v};
        g[u].push_back(v),g[v].push_back(u);
    }
    int now=-1;
    for(int i=1;i<=n;i++){
        if(g[i].size()==2)  now=i;
//      cout<<'!'<<i<<' '<<g[i].size()<<endl;
        col[i]=0;
    }
    if(now==-1){
        puts("No");
        for(int i=1;i<=n;i++){
            g[i].clear(),col[i]=fa[i]=col1[i]=0;
        }
        return;
    }
    puts("Yes"); 
    idx=now;
    int u=1;
    if(now==1)  u=2;    //确定根  
    col[u]=1,dfs(u);
//  return;
    for(int i=1;i<=n;i++){
        g[i].clear(),col[i]=fa[i]=col1[i]=0;
    }
    return;
} 
signed main(){
    int T=read();
    while(T--)  solve();
    return 0;
}//一定要挽回罗琪钧的遗憾啊，一定会挽回罗琪钧的遗憾的！