# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
932992 | ArashJafariyan | Network (BOI15_net) | C++17 | 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>
#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++) {
std::cout << leaf[i] + 1 << ' ' << leaf[i + sz / 2] + 1 << '\n';
}
return 0;
}