#include <bits/stdc++.h>
#define N 500050
#define f first
#define s second
using namespace std;
typedef pair<int, int> pii;
int n, ponte, cnt, id[N], menor[N], root;
vector<int> grafo[N], leaf;
void dfs(int x, int p)
{
menor[x] = x;
for(auto v: grafo[x])
{
if(v == p) continue;
dfs(v, x);
menor[x] = min(menor[v], v);
}
}
void dfs2(int x, int p)
{
vector<pii> order;
if(grafo[x].size() == 1) leaf.push_back(x);
for(auto v: grafo[x])
{
if(v == p) continue;
order.push_back({menor[v], v});
}
sort(order.begin(), order.end());
for(auto v: order) dfs2(v.s, x);
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
cin>>n;
for(int i = 1, a, b; i < n; i++)
{
cin>>a>>b;
grafo[a].push_back(b);
grafo[b].push_back(a);
}
for(int i = 1; i <= n; i++)
{
if(grafo[i].size() <= 1) continue;
root = i;
break;
}
dfs(root, root);
dfs2(root, root);
cout<<(ceil(leaf.size()/2.0))<<"\n";
for(int i = 0, j = leaf.size() - 1; i < leaf.size() and j >= i; i++, j--)
{
if(i == j) cout<<leaf[i]<<" "<<leaf[i + 1]<<"\n";
else cout<<leaf[i]<<" "<<leaf[j]<<"\n";
}
}
Compilation message
net.cpp: In function 'int main()':
net.cpp:74:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0, j = leaf.size() - 1; i < leaf.size() and j >= i; i++, j--)
~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
12024 KB |
Output is correct |
2 |
Incorrect |
14 ms |
12136 KB |
Breaking single line is causing network to disconnect. |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
12024 KB |
Output is correct |
2 |
Incorrect |
14 ms |
12136 KB |
Breaking single line is causing network to disconnect. |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
12024 KB |
Output is correct |
2 |
Incorrect |
14 ms |
12136 KB |
Breaking single line is causing network to disconnect. |
3 |
Halted |
0 ms |
0 KB |
- |