#include <bits/stdc++.h>
using namespace std;
void setup()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
int n, a, b, f[500000];
vector<int> g[500000];
deque<int> temp, l, r;
inline void DFS(int node, int par)
{
f[node] = (g[node].size() == 1);
for (auto &i : g[node])
{
if (i != par)
{
DFS(i, node);
f[node] += f[i];
}
}
}
inline int FindCenter(int node, int par)
{
for (auto &i : g[node])
{
if (i != par && f[i] * 2 > f[0])
{
return FindCenter(i, node);
}
}
return node;
}
inline void Get(int node, int par, deque<int> & inp)
{
if (g[node].size() == 1)
{
inp.push_back(node + 1);
}
for (auto & i : g[node])
{
if (i != par)
{
Get(i, node, inp);
}
}
}
int main()
{
setup();
cin >> n;
for (int i = 0; i < n - 1; ++i)
{
cin >> a >> b;
g[a - 1].push_back(b - 1);
g[b - 1].push_back(a - 1);
}
DFS(0, 0);
a = FindCenter(0, 0);
for (auto & i : g[a])
{
temp.clear();
Get(i, a, temp);
if (l.size() > r.size())
{
for (auto & i : temp)
{
l.push_back(i);
}
}
else
{
for (auto & i : temp)
{
r.push_back(i);
}
}
}
cout << (f[0] + 1) / 2 << "\n";
if (l.size() < r.size())
{
swap(l, r);
}
while (l.size() > r.size() + 1)
{
cout << l.front() << " " << l.back() << "\n";
l.pop_back();
l.pop_front();
}
while (!r.empty())
{
cout << l.back() << " " << r.back() << "\n";
l.pop_back();
r.pop_back();
}
if (!l.empty())
{
cout << a + 1 << " " << l.back();
}
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... |