Submission #1194710

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194710		Hamed_Ghaffari	Network (BOI15_net)	C++20	100 / 100	174 ms	49616 KiB

net

#include <bits/stdc++.h>
using namespace std;

const int MXN = 5e5+5;

int n;
vector<int> g[MXN], ord;

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

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n;
    for(int i=0,u,v; i<n-1; i++) {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int root=1; root<=n; root++) if(g[root].size()>1) {
        dfs(root);
        int sz = ord.size();
        cout << (sz+1)/2 << '\n';
        for(int i=0; i<(sz+1)/2; i++)
            cout << ord[i] << ' ' << ord[(i+sz/2)%sz] << '\n';
        return 0;
    }
    return 0;
}

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