题解：P10921 Happybob's Puzzle (UBC001A)

千花秋雨 · 2024-08-24 22:29:54 · 题解

思路

• 以 1 为根搜索一遍，把深度为奇数的放入集合 A，偶数的放入集合 B。

• 发现当 x,y 之间距离为奇数时，当且仅当 x\in A,y\in B 或者 x\in B,y\in A。

• 因此给两个集合排个序再轮流取数。发现无法轮流取的时候就输出 -1。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
//建树 
int T,n,u,v,h[N],d[N],cnt;
struct node{int nxt,to;}e[N];
void add(int u,int v){ 
    e[++cnt].nxt=h[u];
    e[cnt].to=v;
    h[u]=cnt;
}
//遍历整棵树 
void dfs(int u,int fa){
    for(int i=h[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa)continue;
        d[v]=d[u]+1;//d代表节点深度 
        dfs(v,u);
    }
} 
//两个集合，小根堆维护 
priority_queue<int,vector<int>,greater<int> >S1;
priority_queue<int,vector<int>,greater<int> >S2;
void out1(){//先取第一个集合 
    for(int i=1;i<=n;i++){
        if(i&1){cout<<S1.top()<<" ";S1.pop();continue;}
        else{cout<<S2.top()<<" ";S2.pop();continue;}
    } 
    cout<<"\n";return;
}
void out2(){//先取第二个集合 
    for(int i=1;i<=n;i++){
        if(i&1){cout<<S2.top()<<" ";S2.pop();continue;}
        else{cout<<S1.top()<<" ";S1.pop();continue;}
    } 
    cout<<"\n";return;
}
void clear(){//清空队列 
    while(!S1.empty())S1.pop();
    while(!S2.empty())S2.pop();
}
int main(){
    cin>>T;
    while(T--){
        cin>>n;cnt=0;//清空 
        memset(e,0,sizeof(e));
        memset(h,0,sizeof(h));
        memset(d,0,sizeof(d));
        clear();
        //输入建树 
        for(int i=1;i<n;i++){cin>>u>>v;add(u,v);add(v,u);}
        d[1]=0;dfs(1,0);
        //如果深度奇数放入S1,否则S2 
        for(int i=1;i<=n;i++){
            if(d[i]&1)S1.push(i);//x&1==1代表x是奇数，否则偶数 
            else S2.push(i);
        }
        //两个集合大小 
        int cnt1=S1.size(),cnt2=S2.size();
        if(n&1){//n奇数，无法使两个集合一样多 
            if(max(cnt1,cnt2)-min(cnt1,cnt2)!=1){cout<<"-1\n";continue;}
            //模拟一下发现，cnt1和cnt2只能相差1，不然不可能轮流取
            //且必须先从多的那个集合开始取    
            if(cnt1>cnt2){out1();continue;}
            else{out2();continue;}  
            continue;
        }
        //否则n为偶数时 
        if(cnt1!=cnt2){cout<<"-1\n";continue;}//不相等就无法轮流取 
        out2();continue;//因为d[1]=0，且1是字典序最小的节点，所以从集合2开始输出 
    }
    return 0;
}