제출 #1347183

#제출 시각아이디문제언어결과실행 시간메모리
1347183MunkhturErdenebatNetwork (BOI15_net)C++20
0 / 100
0 ms344 KiB
#include<bits/stdc++.h>
#include<string.h>
#include <algorithm>
#include <iterator>
#include <set>
#include <stdlib.h>
 #define ll long long
 #define fr first
 #define sc second
 #define pb push_back
 #define YES cout<<"YES"<<endl
 #define NO cout<<"NO"<<endl
 #define endl "\n"
using namespace std;
    ll a,b,c,d,e,f,m,i,j,n,h,g,mid,l,r,ka,dp[1000005],t[205005],q[200005],k[200105];
    map<ll,ll> mee,see;
    map<ll,ll> mii,maa;
    vector<ll> vas[200005],ves[200005],vis,vii;
    string x,y,z,te,to;
    pair<ll,string> wefe;
    stack<ll> munkh;
    multiset<ll> mul;
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]);
    }
    for(i=1 ; i<=a ; i++){
        if(vas[i].size()>1){
            g=i;
            break;
        }
    }
    q[0]=g;
    maa[g]=1;
    l=0;
    r=1;
    for(i=0 ; i<vas[q[l]].size() ; i++){
            if(maa[vas[q[l]][i]]==0){
                q[r]=vas[q[l]][i];
                maa[vas[q[l]][i]]=r;
                r++;
            }
        }
        g=r-1;
        l++;
    while(l<r){
        for(i=0 ; i<vas[q[l]].size() ; i++){
            if(maa[vas[q[l]][i]]==0){
                q[r]=vas[q[l]][i];
                r++;
                maa[vas[q[l]][i]]=maa[q[l]];
            }
        }
        l++;
    }
    m=0;
    for(i=1 ; i<=a ; i++){
        if(vas[i].size()==1){
            ves[maa[i]].pb(i);
            m++;
        }
    }
    cout<<(m+1)/2<<endl;
    h=-1;
    for(i=1 ; i<=g ; i++){
        if(ves[i].size()>1){
            h=i;
            break;
        }
    }
    
    if(g%2==1){
      for(i=1 ; i<g-2 ; i+=2){
        cout<<ves[i][0]<<" "<<ves[i+1][0]<<endl;
    }
        if(h!=g){
            cout<<ves[g-2][0]<<" "<<ves[g-1][0]<<endl;
            cout<<ves[g][0]<<" "<<ves[h][1]<<endl;
        }
        else{
            cout<<ves[g][0]<<" "<<ves[g-1][0]<<endl;
            cout<<ves[g][1]<<" "<<ves[g-2][0]<<endl;
        }
    }
    else{
      for(i=1 ; i<g ; i+=2){
        cout<<ves[i][0]<<" "<<ves[i+1][0]<<endl;
    }
    h=-1;
    }
    for(i=1 ; i<=g ; i++){
        if(i==h){
            j=2;
        }
        else{
            j=1;
        }
        for(j=j; j<ves[i].size() ; j++){
            vis.pb(ves[i][j]);
        }
    }
    for(i=0 ; i<vis.size()-1 ; i+=2){
        cout<<vis[i]<<' '<<vis[i+1]<<endl;
        
    }
    if(vis.size()%2==1){
        cout<<vis[vis.size()-1]<<" "<<ves[1][0]<<endl;
    }
    
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...