Submission #1194706

#TimeUsernameProblemLanguageResultExecution timeMemory
1194706Hamed_GhaffariNetwork (BOI15_net)C++20
0 / 100
5 ms12104 KiB
#include <bits/stdc++.h>
using namespace std;

const int MXN = 5e5+5;

int n;
vector<int> g[MXN], ord;

void dfs(int v, int p=-1) {
    for(int u : g[v])
        if(u!=p)
            dfs(u, v);
    if(g[v].size()==1) ord.push_back(v);
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n;
    for(int i=0,u,v; i<n-1; i++) {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int root=1; root<=n; root++) if(g[root].size()>1) {
        dfs(root);
        int sz = ord.size();
        cout << (sz+1)/2 << '\n';
        for(int i=0; i<sz/2; i++)
            cout << ord[i] << ' ' << ord[i+sz/2] << '\n';
        if(sz&1) cout << root << ' ' << ord.back() << '\n';
        return 0;
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...