# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
932992 | ArashJafariyan | Network (BOI15_net) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}