제출 #1347186

#제출 시각아이디문제언어결과실행 시간메모리
1347186MunkhturErdenebatNetwork (BOI15_net)C++20
0 / 100
2 ms344 KiB
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back

ll a,i,j,g,l,r,h;
ll t[205005], q[200005], k[200105];
map<ll,ll> maa;
vector<ll> vas[200005], ves[200005], vis;

int main(){
    cin>>a;

    for(i=1 ; i<=a-1 ; i++){
        cin>>k[i]>>t[i];
        vas[k[i]].pb(t[i]);
        vas[t[i]].pb(k[i]);
    }

    // find non-leaf root
    for(i=1 ; i<=a ; i++){
        if(vas[i].size()>1){
            g=i;
            break;
        }
    }

    // BFS
    q[0]=g;
    maa[g]=1;
    l=0;
    r=1;

    while(l<r){
        for(ll v : vas[q[l]]){
            if(maa[v]==0){
                q[r]=v;
                maa[v]=maa[q[l]];
                r++;
            }
        }
        l++;
    }

    g = r-1;

    ll m=0;

    // collect leaves
    for(i=1 ; i<=a ; i++){
        if(vas[i].size()==1){
            ves[maa[i]].pb(i);
            m++;
        }
    }

    cout<<(m+1)/2<<"\n";

    // find group with >=2 leaves
    h=-1;
    for(i=1 ; i<=g ; i++){
        if(ves[i].size()>1){
            h=i;
            break;
        }
    }

    // safe pairing
    if(g%2==1){
        for(i=1 ; i<g-2 ; i+=2){
            if(!ves[i].empty() && !ves[i+1].empty())
                cout<<ves[i][0]<<" "<<ves[i+1][0]<<"\n";
        }

        if(g>=3){
            if(!ves[g-2].empty() && !ves[g-1].empty())
                cout<<ves[g-2][0]<<" "<<ves[g-1][0]<<"\n";
        }

        if(h==-1){
            if(!ves[g].empty() && !ves[1].empty())
                cout<<ves[g][0]<<" "<<ves[1][0]<<"\n";
        }
        else{
            if(ves[g].size()>0 && ves[h].size()>1)
                cout<<ves[g][0]<<" "<<ves[h][1]<<"\n";
        }
    }
    else{
        for(i=1 ; i<g ; i+=2){
            if(!ves[i].empty() && !ves[i+1].empty())
                cout<<ves[i][0]<<" "<<ves[i+1][0]<<"\n";
        }
        h=-1;
    }

    // collect remaining leaves
    for(i=1 ; i<=g ; i++){
        int start = (i==h ? 2 : 1);
        for(j=start; j<ves[i].size() ; j++){
            vis.pb(ves[i][j]);
        }
    }

    // pair remaining
    for(i=0 ; i+1<vis.size() ; i+=2){
        cout<<vis[i]<<" "<<vis[i+1]<<"\n";
    }

    if(vis.size()%2==1){
        if(!ves[1].empty())
            cout<<vis.back()<<" "<<ves[1][0]<<"\n";
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...