#include <bits/stdc++.h>
using namespace std;
#include <iostream>
typedef vector<int> vi;
typedef vector<vi> vvi;
#define pb push_back
#define rep(i,a,b) for(int i = a; i < b; i++)
int n;
vvi g;
vi leaf;
int total_leafs;
vvi groups;
void dfs(int x, int p) {
for (auto y : g[x]) {
if (y == p) continue;
dfs(y, x);
leaf[x] += leaf[y];
}
}
bool test(int r) {
if (g[r].size() == 1) return false;
for (auto y : g[r]) if (leaf[y] <= leaf[r]) if (leaf[y] > total_leafs / 2) return false;
if (total_leafs - leaf[r] > total_leafs / 2) return false;
return true;
}
void dfs2(int x, int p, vi & group) {
for (auto y : g[x]) {
if (y == p) continue;
dfs2(y, x, group);
}
if (g[x].size() == 1) group.pb(x);
}
int main() {
cin >> n;
if (n == 2) {
cout << 1 << "\n" << 1 << " " << 2 << endl;
exit(0);
}
g.resize(n);
rep(i,0,n-1) {
int a, b;
cin >> a >> b;
a--;b--;
g[a].pb(b);
g[b].pb(a);
}
leaf.assign(n, 0);
rep(i,0,n) if (g[i].size() == 1) leaf[i] = 1;
int root = 0;
while (leaf[root] > 0) root++;
dfs(root, -1);
total_leafs = leaf[root];
while (!test(root)) root++;
for (auto y : g[root]) {
vi group;
dfs2(y, root, group);
groups.pb(group);
}
priority_queue<pair<int,int>> pq;
int I = 0;
for (auto & gr : groups) {
pq.push({gr.size(), I});
I++;
}
vector<pair<int,int>> ans;
while (true) {
pair<int,int> a = pq.top(); pq.pop();
pair<int,int> b = pq.top(); pq.pop();
if (a.first == 0) break;
if (b.first == 0) {
ans.pb({groups[a.second][0], root});
break;
}
ans.pb({groups[a.second][a.first-1], groups[b.second][b.first-1]});
pq.push({a.first-1, a.second});
pq.push({b.first-1, b.second});
}
cout << ans.size() << endl;
for (auto [a, b] : ans) {
cout << a + 1 << " " << b + 1 << endl;
}
}
Compilation message
net.cpp: In function 'int main()':
net.cpp:99:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
99 | for (auto [a, b] : ans) {
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
284 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
284 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Runtime error |
1 ms |
364 KB |
Execution killed with signal 11 |
22 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
284 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Runtime error |
1 ms |
364 KB |
Execution killed with signal 11 |
22 |
Halted |
0 ms |
0 KB |
- |