Submission #932994

#TimeUsernameProblemLanguageResultExecution timeMemory
932994ArashJafariyanNetwork (BOI15_net)C++17
100 / 100
340 ms38504 KiB
#include <bits/stdc++.h>

#ifdef DEBUG
#include "debug.h"
#else
#define debug(...) 0
#endif

typedef long long ll;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    int n;
    std::cin >> n;

    std::vector<std::vector<int>> adj(n);
    for (int i = 1; i < n; i++) {
        int v, u;
        std::cin >> v >> u;
        v--; u--;
        adj[v].push_back(u);
        adj[u].push_back(v);
    }

    std::vector<int> leaf;
    auto dfs = [&](auto self, int v, int p) -> void {
        if (adj[v].size() == 1) {
            leaf.push_back(v);
        }
        for (int u : adj[v]) {
            if (u != p) {
                self(self, u, v);
            }
        }
    };
    dfs(dfs, 0, 0);

    int sz = leaf.size();
    std::cout << (sz + 1) / 2 << '\n';
    for (int i = 0; i + sz / 2 < sz; i++) {
        std::cout << leaf[i] + 1 << ' ' << leaf[i + sz / 2] + 1 << '\n';
    }

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...