#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
const int N = 500005;
vector<int> g[N],leaf[N];
int par[N],n;
int find(int u) {
int v = u;
while (par[u] != u) u = par[u];
while (v != u) {
int tmp = par[v];
par[v] = u;
v = tmp;
}
return u;
}
void unite(int u,int v) {
u = find(u);
v = find(v);
if (u == v) return;
while ((leaf[u].size() > 1 || leaf[v].size() > 1) && leaf[u].size() && leaf[v].size()) {
cout << leaf[u].back() << " " << leaf[v].back() << "\n";
leaf[u].pop_back();
leaf[v].pop_back();
}
par[v] = u;
while (leaf[v].size()) {
leaf[u].push_back(leaf[v].back());
leaf[v].pop_back();
}
}
void dfs(int u,int p) {
for (int v : g[u]) {
if (v == p) continue;
dfs(v,u);
unite(u,v);
}
}
void solve() {
cin >> n;
for (int i = 0; i < n - 1;i++) {
int u,v;
cin>> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
int r = 1,ans = 0;
for (int i = 1; i <= n;i++) {
par[i] = i;
if (g[i].size() != 1) {
r = i;
}
if (g[i].size() == 1) {
ans++;
leaf[i].push_back(i);
}
}
cout << (ans + 1) / 2 << "\n";
dfs(r,0);
int v = find(r);
if (leaf[v].size() % 2) leaf[v].push_back(r);
for (int i = 0; i < leaf[v].size() / 2;i++) cout << leaf[v][i] <<" " << leaf[v][n - i - 1] << "\n";
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
//cin >> t;
while (t--) {
solve();
cout << "\n";
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |