Submission #1206724

#TimeUsernameProblemLanguageResultExecution timeMemory
1206724dksnfjkfnwkfwNetwork (BOI15_net)C++20
0 / 100
14 ms23880 KiB
#include <bits/stdc++.h> using namespace std; #define sonic ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define pb push_back #define el cout << '\n' using pii = pair<int, int>; const int N = 1e6 + 9; int n; vector<int> adj[N]; int degree[N]; int main() { sonic; cin >> n; for (int i = 1; i < n; ++i) { int u, v; cin >> u >> v; adj[u].pb(v); adj[v].pb(u); degree[u]++; degree[v]++; } // Tìm các lá (đỉnh có bậc = 1) vector<int> leaves; for (int i = 1; i <= n; ++i) { if (degree[i] == 1) { leaves.pb(i); } } vector<pii> res; // Ghép từng cặp lá for (int i = 0; i + 1 < (int)leaves.size(); i += 2) { res.pb({leaves[i], leaves[i + 1]}); } // Nếu số lá lẻ -> còn dư 1 lá, nối nó với 1 đỉnh không phải lá if (leaves.size() % 2 == 1) { int lastLeaf = leaves.back(); for (int i = 1; i <= n; ++i) { if (degree[i] > 1) { res.pb({lastLeaf, i}); break; } } } // Xuất kết quả 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...