# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
830226 | 2023-08-19T00:11:57 Z | yusuf12360 | Network (BOI15_net) | C++14 | 0 ms | 0 KB |
#include<bits/stdc++.h> #define int long long using namespace std; int cnt; vector<int> leaf; vector<vector<int>> adj; void dfs(int u, int p=-1) { if(adj[u].size()==1) leaf.push_back(u), cnt++; for(int pp : adj[u]) { if(pp==p) continue; dfs(pp, u) } } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; adj.resize(n); vector<pair<int, int>> ans; map<int, int> mp; for(int i=1; i<n; i++) { int u, v; cin >> u >> v; --u; --v; adj[u].push_back(v); adj[v].push_back(u); } dfs(0); for(int i=0; 2*i<cnt; i++) ans.push_back({leaf[i], leaf[i+cnt/2]}); cout << ans.size() << '\n'; for(auto p : ans) cout << p.first+1 << ' ' << p.second+1 << '\n'; return 0; }