Submission #1173927

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173927		LucaIlie	Network (BOI15_net)	C++20	0 / 100	5 ms	12100 KiB

net

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 5e5;
vector<int> adj[MAX_N + 1];

vector<int> order;

void dfs( int u, int p ) {
    if ( adj[u].size() == 1 )
        order.push_back( u );
    for ( int v: adj[u] ) {
        if ( v == p )
            continue;
        dfs( v, u );
    }
}

int main() {
    cin.tie( nullptr );
    ios_base::sync_with_stdio( false );

    int n;

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

    int r = 1;
    while ( adj[r].size() == 1 )
        r++;

    dfs( r, 0 );

    cout << (order.size() + 1) / 2 << "\n";
    for ( int i = 0; i < order.size() / 2; i++ )
        cout << order[i] << " " << order[order.size() - 1 - i] << "\n";
    if ( order.size() % 2 == 1 )
        cout << order[order.size() / 2] << " " << order[1] << "\n";
    

    return 0;
}

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