Submission #1150487

#TimeUsernameProblemLanguageResultExecution timeMemory
1150487The_SamuraiNetwork (BOI15_net)C++20
0 / 100
0 ms324 KiB
// I stand with PALESTINE




// #pragma GCC optimize("Ofast,O3")
// #pragma GCC target("avx,avx2")
#include "bits/stdc++.h"

using namespace std;
using ll = long long;

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> g(n + 1);
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    int root = 1;
    while (g[root].size() == 1) root++;
    vector<int> vec;
    auto dfs = [&](auto &dfs, int u, int p) -> void {
        if (g[u].size() == 1) vec.emplace_back(u);
        for (int v: g[u]) {
            if (v != p) dfs(dfs, v, u);
        }
    };
    dfs(dfs, root, -1);
    cout << (vec.size() + 1) / 2 << '\n';
    int l = 0, r = vec.size() - 1;
    while (l < r) {
        cout << vec[l] << ' ' << vec[r] << '\n';
        l++, r--;
    }
    if (l <= r) cout << vec[0] << ' ' << vec[l] << '\n';
}

int main() {
    cin.tie(0)->sync_with_stdio(false);
#ifdef sunnatov
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int q = 1;
    // cin >> q;
    while (q--) {
        solve();
        // cout << '\n';
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...