Submission #1149451

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149451		njoop	Network (BOI15_net)	C++17	100 / 100	271 ms	45452 KiB

net

#include <bits/stdc++.h>

using namespace std;

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

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

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);
            break;
        }
    }
    cout << leaf.size()/2 + leaf.size()%2 << "\n";
    for(int i=0; i<leaf.size()/2; i++) {
        cout << leaf[i] << " " << leaf[i + leaf.size()/2] << "\n";
    }
    if(leaf.size()%2 == 1) {
        cout << leaf[0] << " " << leaf[leaf.size()-1] << "\n";
    }
    return 0;
}

• Subtask 1: 18 / 18
• Subtask 2: 45 / 45
• Subtask 3: 37 / 37