제출 #1186894

#제출 시각아이디문제언어결과실행 시간메모리
1186894JooNetwork (BOI15_net)C++20
0 / 100
5 ms12100 KiB
#include <bits/stdc++.h>
using namespace std;

const int MXN = 5e5 + 10;

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

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

    if (G[u].size() == 1) {
        deg_one.emplace_back(dep[u], 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 l = 0, r = (int)deg_one.size() - 1;
    vector<pair<int, int>> ans;
    for (; l < r; l++, r--) {
        auto [dep_u, u] = deg_one[l];
        auto [dep_v, v] = deg_one[r];
        ans.emplace_back(u, v);
    }

    if (l == r) {
        ans.emplace_back(1, deg_one[l].second);
    }

    cout << ans.size() << "\n";
    for (auto [u, v] : ans) {
        cout << u << " " << v << "\n";
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...