Submission #1150488

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150488		The_Samurai	Network (BOI15_net)	C++20	100 / 100	229 ms	36732 KiB

net

// 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) / 2;
    while (r < vec.size()) {
        cout << vec[l] << ' ' << vec[r] << '\n';
        l++, r++;
    }
    if (vec.size() % 2) 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';
    }
}

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