Submission #1187286

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187286		Joo	Network (BOI15_net)	C++20	0 / 100	0 ms	328 KiB

net

#include <iostream>
#include <vector>
using namespace std;

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

    // Find leaves (nodes with degree 1)
    vector<int> leaves;
    for (int i = 1; i <= n; ++i) {
        if (graph[i].size() == 1) {
            leaves.push_back(i);
        }
    }

    vector<pair<int, int>> result;

    // Pair up leaves
    for (size_t i = 0; i + 1 < leaves.size(); i += 2) {
        result.emplace_back(leaves[i], leaves[i + 1]);
    }

    // If odd number of leaves, connect the last one to the root (or any node with degree > 1)
    if (leaves.size() % 2 == 1) {
        for (int i = 1; i <= n; ++i) {
            if (graph[i].size() > 1) {
                result.emplace_back(leaves.back(), i);
                break;
            }
        }
    }

    // Output
    cout << result.size() << endl;
    for (auto [u, v] : result) {
        cout << u << " " << v << endl;
    }

    return 0;
}

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