Submission #1186902

#TimeUsernameProblemLanguageResultExecution timeMemory
1186902JooNetwork (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<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";
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...