# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
932991 | 2024-02-24T17:35:59 Z | ArashJafariyan | Network (BOI15_net) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h> #ifdef DEBUG #include "debug.h" #else #define debug(...) 0 #endif typedef long long ll; int main() { std::ios::sync_with_stdio(0); std::cin.tie(0); int n; std::cin >> n; std::vector<std::vector<int>> adj(n); for (int i = 1; i < n; i++) { int v, u; std::cin >> v >> u; v--; u--; adj[v].push_back(u); adj[u].push_back(v); } std::vector<int> leaf; auto dfs = [&](auto self, int v, int p) -> void { if (adj[v].size() == 1) { leaf.push_back(v); } for (int u : adj[v]) { if (u != p) { self(self, u, v); } } }; dfs(dfs, 0, 0); int sz = leaf.size(); cout << (sz + 1) / 2 << '\n'; for (int i = 0; i + sz / 2 < sz; i++) { cout << leaf[i] + 1 << ' ' << leaf[i + sz / 2] + 1 << '\n'; } return 0; }