제출 #1186902

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1186902		Joo	Network (BOI15_net)	C++20	0 / 100	5 ms	12100 KiB

net

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

const int MXN = 5e5 + 10;

vector<int> G[MXN];
vector<int> deg_one;
int dep[MXN];

void dfs(int u, int p) {
    if (G[u].size() == 1) {
        deg_one.emplace_back(u);
    }

    for (int v : G[u]) {
        if (v == p) continue;
        dep[v] = dep[u] + 1;
        dfs(v, u);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n; cin >> n;
    for (int i = 1; i <= n - 1; i++) {
        int u, v; cin >> u >> v;
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }

    dfs(1, -1);

    int ans = (deg_one.size() + 1) / 2;
    cout << ans << "\n";
    int l = 0, r = (int)deg_one.size() - 1;
    for (; l < r; l++, r--) {
        cout << deg_one[l] << " " << deg_one[r] << "\n";
    }
    if (l == r) {
        cout << 1 << " " << deg_one[l] << "\n";
    }
}

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