Submission #1149443

#TimeUsernameProblemLanguageResultExecution timeMemory
1149443njoopNetwork (BOI15_net)C++17
0 / 100
6 ms12104 KiB
#include <bits/stdc++.h>

using namespace std;

int n, s, t, l, r;
vector<int> g[500010];
vector<pair<int, int>> leaf;

void dfs(int no, int pa, int di) {
    if(g[no].size() == 1) {
        leaf.push_back({di, no});
    }
    for(auto i: g[no]) {
        if(i == pa) continue;
        dfs(i, no, di+1);
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for(int i=1; i<n; i++) {
        cin >> s >> t;
        g[s].push_back(t);
        g[t].push_back(s);
    }
    for(int i=1; i<=n; i++) {
        if(g[i].size() > 1) {
            dfs(i, -1, 0);
            break;
        }
    }
    sort(leaf.begin(), leaf.end());
    cout << leaf.size()/2 + leaf.size()%2 << "\n";
    l=0, r=leaf.size()-1;
    while(l <= r) {
        if(l == r) cout << leaf[0].second << " " << leaf[l].second << "\n";
        else cout << leaf[l].second << " " << leaf[r].second << "\n";
        l++;
        r--;
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...