제출 #917656

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
917656		VMaksimoski008	Network (BOI15_net)	C++14	100 / 100	654 ms	41260 KiB

net

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

int n, a, b, i;
vector<vector<int> > G(500005);
vector<int> L;

void dfs(int u, int p) {
    for(int &v : G[u])
        if(v != p) dfs(v, u);
    if(G[u].size() == 1) L.push_back(u);
}

int main() {
    cin >> n;

    for(i=0; i<n-1; i++) {
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    dfs(1, 0);

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

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