Submission #107194

#	Time	Username	Problem	Language	Result	Execution time	Memory
107194		dolphingarlic	Network (BOI15_net)	C++17	0 / 100	13 ms	12160 KiB

net

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define FOR(i, x, y) for(ll i = x; i < y; i++)
typedef long long ll;
using namespace std;

vector<ll> graph[500001], leaves;

void dfs(ll node, ll parent = 0) {
    if (graph[node].size() == 1) leaves.push_back(node);
    for (auto& i : graph[node]) {
        if (i == parent) continue;
        dfs(i, node);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n;
    cin >> n;
    FOR(i, 0, n - 1) {
        ll a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    dfs(1);
    cout << (leaves.size() + 1) / 2 << endl;
    FOR(i, 0, (ll)(leaves.size() / 2)) cout << leaves[i] << ' ' << leaves[leaves.size() - i - 1] << endl;
    if (leaves.size() & 1) cout << leaves[leaves.size() / 2] << " 1" << endl;
    return 0;
}

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