제출 #1111484

#제출 시각아이디문제언어결과실행 시간메모리
1111484Kirill22Network (BOI15_net)C++17
100 / 100
375 ms44216 KiB
#include "bits/stdc++.h" using namespace std; void solve() { int n; cin >> n; vector<vector<int>> g(n); for (int i = 0, x, y; i + 1 < n; i++) { cin >> x >> y; x--, y--; g[x].push_back(y); g[y].push_back(x); } int rt = 0; while ((int) g[rt].size() == 1) { rt++; } vector<int> leafes; auto dfs = [&] (auto&& dfs, int v, int pr) -> void { if ((int) g[v].size() == 1) { leafes.push_back(v); } for (auto u : g[v]) { if (u != pr) { dfs(dfs, u, v); } } }; dfs(dfs, 0, 0); int sz = (int) leafes.size(); vector<pair<int, int>> ans; if (sz % 2 == 0) { for (int i = 0; i < sz / 2; i++) { ans.push_back({leafes[i], leafes[i + sz / 2]}); } } else { for (int i = 0; i < sz / 2; i++) { ans.push_back({leafes[i], leafes[i + sz / 2]}); } ans.push_back({leafes[0], leafes.back()}); } cout << (int) ans.size() << '\n'; for (auto& [x, y] : ans) { cout << x + 1 << " " << y + 1 << '\n'; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; // cin >> t; while (t--) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...