Submission #1301990

#TimeUsernameProblemLanguageResultExecution timeMemory
1301990PakinDioxideNetwork (BOI15_net)C++17
0 / 100
0 ms332 KiB
#include <bits/stdc++.h>
#define ll long long

using namespace std;

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n; cin >> n;
    vector <int> adj[n+1];
    for (int i = 1, u, v; i < n; i++) cin >> u >> v, adj[u].emplace_back(v), adj[v].emplace_back(u);
    auto bfs = [&] (int st) {
        queue <int> q;
        int vis[n+1]; memset(vis, 0, sizeof(vis));
        int rc = -1;
        q.emplace(st);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            rc = u;
            for (auto v : adj[u]) if (!vis[v]) q.emplace(v), vis[v] = 1;
        }
        return rc;
    };
    int D1 = bfs(1);
    int D2 = bfs(D1);
    int dia[n+1]; memset(dia, 0, sizeof(dia));
    function <int(int, int)> fd = [&] (int u, int p) {
        dia[u] = (u == D1 || u == D2);
        for (auto v : adj[u]) if (v != p) dia[u] = max(dia[u], fd(v, u));
        return dia[u];
    };
    fd(D1, D1);
    vector <vector <int>> V;
    function <void(int, int, vector <int> &)> dfs = [&] (int u, int p, vector <int> &k) {
        for (auto v : adj[u]) if (v != p && !dia[v]) k.emplace_back(v), dfs(v, u, k);
    };
    for (int i = 1; i <= n; i++) if (dia[i]) {
        vector <int> k;
        dfs(i, i, k);
        if (k.size()) V.emplace_back(k);
    }
    vector <pair <int, int>> ans;
    int ss = 0, sz = V.size();
    for (auto &e : V) {
        if (e.size() >= 2) {
            int u = e.back(); e.pop_back();
            int v = e.back(); e.pop_back();
            ss = 1;
            ans.emplace_back(u, D1);
            ans.emplace_back(v, D2);
            if (e.empty()) e.swap(V[--sz]);
            break;
        }
    }
    while (sz > 1) {
        ans.emplace_back(V[0].back(), V[1].back());
        V[0].pop_back();
        V[1].pop_back();
        cerr << sz << '\n';
        if (V[0].empty()) V[0].swap(V[--sz]);
        if (V[1].empty()) V[1].swap(V[--sz]);
    }
    while (!V[0].empty()) ans.emplace_back(V[0].back(), D1), V[0].pop_back();
    if (!ss) ans.emplace_back(D1, D2);
    cout << ans.size() << '\n';
    for (auto &[x, y] : ans) cout << x << ' ' << y << '\n';
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...