Submission #1140841

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140841		huoi	Network (BOI15_net)	C++17	0 / 100	0 ms	328 KiB

net

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define INF 9e18

void solve() {
    int n;
    cin >> n;

    vector<vector<int>> adj(n);
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v; u--, v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<bool> leaf(n);
    for (int u = 0; u < n; u++) {
        if (adj[u].size() == 1) {
            leaf[u] = true;
        }
    }

    vector<bool> vis(n); // applies only to leaves
    function<pair<int, int>(int, int, int)> dfs = [&](int u, int p, int d) {
        int max_dist = -INF;
        int ans_node = -1;
        if (p != -1 && leaf[u] && !vis[u]) {
            //printf("found  leaf\n");
            return make_pair(u, d);
        }
        for (int v : adj[u]) {
            if (v == p) continue;
            //printf("%lld\n", v + 1);
            auto [leaf, dist] = dfs(v, u, d + 1);
            if (dist > max_dist) {
                max_dist = dist;
                ans_node = leaf;
            }
        }
        return make_pair(ans_node, max_dist);
    };

    vector<pair<int, int>> ans;
    int first_leaf = -1;
    for (int u = 0; u < n; u++) {
        if (!leaf[u]) continue;
        if (first_leaf == -1) first_leaf = u;
        if (vis[u]) continue;
        vis[u] = true;
        int v = dfs(u, -1, 0).first;
        if (v != -1) {
            vis[v] = true;
        } else {
            v = first_leaf;
        }
        ans.push_back({u, v});
    }

    cout << ans.size() << "\n";
    for (auto [u, v] : ans) {
        cout << u + 1<< " " << v + 1 << "\n";
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

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