제출 #1272904

#제출 시각아이디문제언어결과실행 시간메모리
1272904SP_CaramenNetwork (BOI15_net)C++20
0 / 100
0 ms14392 KiB
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    if (!(cin >> n)) return 0;
    vector<vector<int>> adj(n+1);
    for (int i = 0; i < n-1; ++i) {
        int a,b; cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    vector<int> leaves;
    for (int v = 1; v <= n; ++v) {
        if ((int)adj[v].size() == 1) leaves.push_back(v);
    }

    int L = (int)leaves.size();
    int k = (L + 1) / 2; // ceil(L/2)
    cout << k << '\n';

    // pair symmetric leaves from ends; if odd, connect middle with leaves[0]
    for (int i = 0; i < L/2; ++i) {
        cout << leaves[i] << ' ' << leaves[L-1-i] << '\n';
    }
    if (L % 2 == 1) {
        cout << leaves[L/2] << ' ' << leaves[0] << '\n';
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...