# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
830226 | yusuf12360 | Network (BOI15_net) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}