Submission #1189533

#TimeUsernameProblemLanguageResultExecution timeMemory
1189533heheNetwork (BOI15_net)C++20
100 / 100
379 ms45384 KiB
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> adj(500003);
vector<int> margini;

void dfs(int node, int parent){
    if(adj[node].size() == 1){
        margini.push_back(node);
    }
    for(int i : adj[node]){
        if(i != parent){
            dfs(i, node);}
    }
}

int main(){
    int n; cin >> n;
    int a, b;
    
    for(int i = 0; i < n - 1; i++){
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    
    dfs(1, 0);
    
    int marime = margini.size();
    
    int middle = marime / 2;
    
    cout << marime / 2 + marime % 2 << '\n';
    
    for(int i = 0; i < middle; i++){
        cout << margini[i] << ' ' << margini[i + middle] << '\n';
    }
    
    if(marime % 2 == 1){
        cout << margini[0] << ' ' << margini[marime - 1];
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...