Submission #1186900

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186900		Joo	Network (BOI15_net)	C++20	100 / 100	273 ms	51612 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);

    deg_one.emplace_back(1);
    int ans = (deg_one.size() / 2);
    cout << ans << "\n";
    for (int i = 0; i < ans; i++) {
        cout << deg_one[i] << " " << deg_one[i + ans] << "\n";
    }
}

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