Submission #1171928

#TimeUsernameProblemLanguageResultExecution timeMemory
1171928NewtonabcNetwork (BOI15_net)C++20
100 / 100
461 ms45280 KiB
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
vector<int> adj[N];
vector<int> lf;
void dfs(int u,int p=-1){
    if(adj[u].size()==1) lf.push_back(u);
    for(auto v:adj[u]){
        if(v==p) continue;
        dfs(v,u);
    }
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n-1;i++){
        int u,v;
        cin>>u >>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1);
    int sz=lf.size();
    // for(auto tmp:lf){
    //     cout<<tmp <<" " ;
    // }
    // cout<<"\n";
    cout<<(sz+1)/2 <<"\n";
    for(int i=0;i<(sz/2);i++){
        cout<<lf[i] <<" " <<lf[i+((sz+1)/2)] <<"\n";
    }
    if(sz%2) cout<<1 <<" " <<lf[sz/2];
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...