Submission #1206745

#TimeUsernameProblemLanguageResultExecution timeMemory
1206745dksnfjkfnwkfwNetwork (BOI15_net)C++20
0 / 100
5 ms12104 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 5e5 + 5; int n; vector<int> adj[MAXN]; int deg[MAXN]; bool used[MAXN]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n; for (int i = 1; i < n; ++i) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); deg[u]++; deg[v]++; } // Tìm các lá vector<int> leaves; for (int i = 1; i <= n; ++i) { if (deg[i] == 1) leaves.push_back(i); } vector<pair<int, int>> res; int L = leaves.size(); // Ghép cặp các lá for (int i = 0; i + 1 < L; i += 2) { res.emplace_back(leaves[i], leaves[i + 1]); used[leaves[i]] = used[leaves[i + 1]] = true; } // Nếu số lá lẻ → còn một lá chưa ghép if (L % 2 == 1) { int last = -1; for (int i = 1; i <= n; ++i) { if (!used[i] && deg[i] > 1) { last = i; break; } } res.emplace_back(leaves.back(), last); } // Output cout << res.size() << '\n'; for (auto [u, v] : res) { cout << u << ' ' << v << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...