Submission #1206746

#TimeUsernameProblemLanguageResultExecution timeMemory
1206746dksnfjkfnwkfwNetwork (BOI15_net)C++20
0 / 100
6 ms12104 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 5e5 + 5; int n; vector<int> adj[MAXN]; int deg[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]++; } // Bước 1: Tìm 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(); // Bước 2: Ghép cặp các lá for (int i = 0; i + 1 < L; i += 2) { res.emplace_back(leaves[i], leaves[i + 1]); } // Bước 3: Nếu số lá lẻ → ghép lá cuối với đỉnh bất kỳ bậc ≥ 2 if (L % 2 == 1) { int last_leaf = leaves.back(); for (int i = 1; i <= n; ++i) { if (deg[i] > 1) { res.emplace_back(last_leaf, i); break; } } } // 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...