제출 #430479

#제출 시각아이디문제언어결과실행 시간메모리
430479OptxPrimeNetwork (BOI15_net)C++11
0 / 100
1 ms308 KiB
#include<iostream>
#include<bits/stdc++.h>

using namespace std;
#define pb push_back
#define mp make_pair

bool visited[1000010];
vector<vector<int>> adj;
vector<int> listovi;

void dfs(int x)
{
    visited[x] = true;
    if( adj[x].size()==1 )
        listovi.pb(x);
    for( auto u : adj[x]){
        if(!visited[u])
            dfs(u);
    }
}

int main(){

    int n,a,b;
    cin>>n;
    adj.resize(n);
    for(int i=0;i<n-1;i++){
        cin>>a>>b;
        a--;
        b--;
        adj[a].pb(b);
        adj[b].pb(a);
    }

    dfs(0);
   // cout << " stigo " <<endl;
    int sz = listovi.size();
    cout << (sz+ 1)/2 <<endl;
   // cout << sz << endl;
    for(int i=0;i<sz/2;i++ ){
        cout << listovi[i]+1 <<" " << listovi[ sz-1-i ]+1<<endl;
    }
    if( sz%2==1 ){
        cout << listovi[sz/2]+1 << " " << listovi[0]+1 << endl;
    }

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...