Submission #634779

#	Time	Username	Problem	Language	Result	Execution time	Memory
634779		tvladm2009	Network (BOI15_net)	C++14	100 / 100	611 ms	65464 KiB

net

#include <iostream>
#include <vector>

using namespace std;

const int MAX_N = 5 * 1e5;
vector<int> g[MAX_N + 1], leaves;
int n;

void dfs(int u, int p = -1) {
    for (int v : g[u]) {
        if (v != p) {
            dfs(v, u);
        }
    }
    if (g[u].size() == 1) {
        leaves.push_back(u);
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int root = 0;
    for (int i = 1; i <= n; i++) {
        if (g[i].size() > 1) {
            root = i;
        }
    }
    dfs(root);
    cout << (leaves.size() + 1) / 2 << "\n";
    int cnt = leaves.size() / 2;
    for (int i = 0; i < cnt; i++) {
        cout << leaves[i] << " " << leaves[i + cnt + leaves.size() % 2] << "\n";
    }
    if (leaves.size() % 2 == 1) {
        cout << root << " " << leaves[cnt] << "\n";
    }
    return 0;
}

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