#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <utility>
using namespace std;
int n;
vector<int> graph[500005];
int start;
int leaves[500005];
int et[500005]; int marker = 0;
int etrev[500005];
int bit[500005];
void upd(int n, int inc) {
n++;
while (n < 500005) {
bit[n] += inc;
n += (n&-n);
}
}
int find(int n) {
int s = 0;
n++;
while (n > 0) {
s += bit[n];
n -= (n&-n);
}
return s;
}
int findfirst(int n) {
if (graph[n].size()==1) return etrev[n];
int l = 0, r = 500005, v = find(etrev[n]);
int best = 500004;
while (l < r) {
int m = (l+r)/2;
if (find(m) > v) {
best = m; r = m;
} else l = m+1;
}
return best;
}
int leaffind(int n, int p) {
et[marker] = n; marker++;
etrev[et[marker-1]] = marker-1;
int vis = 0;
for (int i : graph[n]) {
if (i == p) continue;
vis += leaffind(i, n);
}
if (vis == 0) {
leaves[n] = 1;
upd(marker-1, 1);
return 1;
}
leaves[n] = vis;
return vis;
}
vector<pair<int, int>> pairs;
void findans(int n, int p, int reps) {
int max = 0, pos = 0, sum = 0;
for (int i : graph[n]) {
if (i == p) continue;
sum += leaves[i];
if (leaves[i] > max) {
max = leaves[i];
pos = i;
}
}
int pairable = min(sum, (sum-max)*2);
if (reps > pairable) {
findans(pos, n, reps-pairable);
leaves[pos] = sum-max;
reps -= (reps-pairable);
}
/*
PriorityQueue<int[]> pq = new PriorityQueue<>(new SortArr());
for (int i : graph[n]) {
if (i == p) continue;
pq.add(new int[] {i, leaves[i]});
}
while (reps > 1) {
int[] data1 = pq.poll();
int[] data2 = pq.poll();
int pos1 = findfirst(data1[0]);
int pos2 = findfirst(data2[0]);
upd(pos1, -1); upd(pos2, -1);
pairs.add(new int[] {et[pos1]+1, et[pos2]+1});
if (data1[1] > 1) pq.add(new int[] {data1[0], data1[1]-1});
if (data2[1] > 1) pq.add(new int[] {data2[0], data2[1]-1});
reps -= 2;
}
if (reps == 1) {
int[] data1 = pq.poll();
int pos1 = findfirst(data1[0]);
upd(pos1, -1);
pairs.add(new int[] {et[pos1]+1, n+1});
}*/
int maxleaves = 0;
for (int i : graph[n]) {
if (i==p) continue;
maxleaves = std::max(maxleaves, leaves[i]);
}
vector<int> stack[maxleaves+1];
for (int i = 0; i < maxleaves+1; i++) {
vector<int> temp;
stack[i] = temp;
}
max = 0; int max2 = 0;
for (int i : graph[n]) {
if (i==p) continue;
stack[leaves[i]].push_back(i);
if (leaves[i] > max) {
max2 = max; max = leaves[i];
} else if (leaves[i] > max2) max2 = leaves[i];
}
while (reps > 1) {
pair<int, int> data1{stack[max].back(), max};
stack[max].pop_back();
pair<int, int> data2{stack[max2].back(), max2};
stack[max2].pop_back();
int pos1 = findfirst(data1.first);
int pos2 = findfirst(data2.first);
upd(pos1, -1); upd(pos2, -1);
pairs.push_back({et[pos1]+1, et[pos2]+1});
if (data1.second > 1) {
stack[data1.second-1].push_back(data1.first);
}
if (data2.second > 1) {
stack[data2.second-1].push_back(data2.first);
}
if (stack[max].size() == 0) max--;
if (stack[max2].size() == 0) max2--;
if (max2 == max && stack[max].size() == 1) max2--;
reps -= 2;
}
if (reps == 1) {
pair<int, int> data1{stack[max].back(), max};
stack[max].pop_back();
int pos1 = findfirst(data1.first);
upd(pos1, -1);
pairs.push_back({et[pos1]+1, n+1});
}
}
int main() {
cin >> n;
for (int i = 0; i < 500005; i++) {
vector<int> temp;
graph[i] = temp;
}
for (int i = 0; i < n-1; i++) {
int a, b; cin >> a >> b; a--; b--;
graph[a].push_back(b);
graph[b].push_back(a);
}
for (int i = 0; i < 500005; i++) {
if (graph[i].size() > 1) {
start = i; break;
}
}
leaffind(start, -1);
findans(start, -1, leaves[start]);
cout << (pairs.size()) << "\n";
for (pair<int, int> i : pairs) {
cout << (i.first) << " " << (i.second) << "\n";
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
12140 KB |
Output is correct |
2 |
Correct |
12 ms |
12140 KB |
Output is correct |
3 |
Correct |
12 ms |
12140 KB |
Output is correct |
4 |
Correct |
12 ms |
12140 KB |
Output is correct |
5 |
Correct |
12 ms |
12140 KB |
Output is correct |
6 |
Correct |
12 ms |
12140 KB |
Output is correct |
7 |
Correct |
12 ms |
12140 KB |
Output is correct |
8 |
Correct |
12 ms |
12140 KB |
Output is correct |
9 |
Correct |
12 ms |
12140 KB |
Output is correct |
10 |
Correct |
13 ms |
12140 KB |
Output is correct |
11 |
Correct |
12 ms |
12140 KB |
Output is correct |
12 |
Correct |
12 ms |
12140 KB |
Output is correct |
13 |
Correct |
15 ms |
12140 KB |
Output is correct |
14 |
Correct |
12 ms |
12140 KB |
Output is correct |
15 |
Correct |
13 ms |
12140 KB |
Output is correct |
16 |
Correct |
12 ms |
12140 KB |
Output is correct |
17 |
Correct |
12 ms |
12140 KB |
Output is correct |
18 |
Correct |
12 ms |
12140 KB |
Output is correct |
19 |
Correct |
12 ms |
12160 KB |
Output is correct |
20 |
Correct |
12 ms |
12140 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
12140 KB |
Output is correct |
2 |
Correct |
12 ms |
12140 KB |
Output is correct |
3 |
Correct |
12 ms |
12140 KB |
Output is correct |
4 |
Correct |
12 ms |
12140 KB |
Output is correct |
5 |
Correct |
12 ms |
12140 KB |
Output is correct |
6 |
Correct |
12 ms |
12140 KB |
Output is correct |
7 |
Correct |
12 ms |
12140 KB |
Output is correct |
8 |
Correct |
12 ms |
12140 KB |
Output is correct |
9 |
Correct |
12 ms |
12140 KB |
Output is correct |
10 |
Correct |
13 ms |
12140 KB |
Output is correct |
11 |
Correct |
12 ms |
12140 KB |
Output is correct |
12 |
Correct |
12 ms |
12140 KB |
Output is correct |
13 |
Correct |
15 ms |
12140 KB |
Output is correct |
14 |
Correct |
12 ms |
12140 KB |
Output is correct |
15 |
Correct |
13 ms |
12140 KB |
Output is correct |
16 |
Correct |
12 ms |
12140 KB |
Output is correct |
17 |
Correct |
12 ms |
12140 KB |
Output is correct |
18 |
Correct |
12 ms |
12140 KB |
Output is correct |
19 |
Correct |
12 ms |
12160 KB |
Output is correct |
20 |
Correct |
12 ms |
12140 KB |
Output is correct |
21 |
Correct |
12 ms |
12140 KB |
Output is correct |
22 |
Correct |
14 ms |
12268 KB |
Output is correct |
23 |
Correct |
14 ms |
12268 KB |
Output is correct |
24 |
Correct |
15 ms |
12268 KB |
Output is correct |
25 |
Correct |
14 ms |
12268 KB |
Output is correct |
26 |
Correct |
14 ms |
12268 KB |
Output is correct |
27 |
Correct |
15 ms |
12268 KB |
Output is correct |
28 |
Correct |
14 ms |
12268 KB |
Output is correct |
29 |
Correct |
14 ms |
12268 KB |
Output is correct |
30 |
Correct |
13 ms |
12140 KB |
Output is correct |
31 |
Correct |
17 ms |
12268 KB |
Output is correct |
32 |
Correct |
12 ms |
12140 KB |
Output is correct |
33 |
Correct |
12 ms |
12140 KB |
Output is correct |
34 |
Correct |
12 ms |
12140 KB |
Output is correct |
35 |
Correct |
12 ms |
12140 KB |
Output is correct |
36 |
Correct |
12 ms |
12140 KB |
Output is correct |
37 |
Correct |
13 ms |
12140 KB |
Output is correct |
38 |
Correct |
13 ms |
12268 KB |
Output is correct |
39 |
Correct |
12 ms |
12140 KB |
Output is correct |
40 |
Correct |
12 ms |
12140 KB |
Output is correct |
41 |
Correct |
13 ms |
12140 KB |
Output is correct |
42 |
Correct |
13 ms |
12140 KB |
Output is correct |
43 |
Correct |
13 ms |
12140 KB |
Output is correct |
44 |
Correct |
13 ms |
12140 KB |
Output is correct |
45 |
Correct |
13 ms |
12140 KB |
Output is correct |
46 |
Correct |
13 ms |
12140 KB |
Output is correct |
47 |
Correct |
12 ms |
12128 KB |
Output is correct |
48 |
Correct |
12 ms |
12140 KB |
Output is correct |
49 |
Correct |
14 ms |
12268 KB |
Output is correct |
50 |
Correct |
16 ms |
12140 KB |
Output is correct |
51 |
Correct |
12 ms |
12140 KB |
Output is correct |
52 |
Correct |
13 ms |
12140 KB |
Output is correct |
53 |
Correct |
13 ms |
12140 KB |
Output is correct |
54 |
Correct |
12 ms |
12176 KB |
Output is correct |
55 |
Correct |
13 ms |
12140 KB |
Output is correct |
56 |
Correct |
13 ms |
12140 KB |
Output is correct |
57 |
Correct |
14 ms |
12140 KB |
Output is correct |
58 |
Correct |
14 ms |
12268 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
12140 KB |
Output is correct |
2 |
Correct |
12 ms |
12140 KB |
Output is correct |
3 |
Correct |
12 ms |
12140 KB |
Output is correct |
4 |
Correct |
12 ms |
12140 KB |
Output is correct |
5 |
Correct |
12 ms |
12140 KB |
Output is correct |
6 |
Correct |
12 ms |
12140 KB |
Output is correct |
7 |
Correct |
12 ms |
12140 KB |
Output is correct |
8 |
Correct |
12 ms |
12140 KB |
Output is correct |
9 |
Correct |
12 ms |
12140 KB |
Output is correct |
10 |
Correct |
13 ms |
12140 KB |
Output is correct |
11 |
Correct |
12 ms |
12140 KB |
Output is correct |
12 |
Correct |
12 ms |
12140 KB |
Output is correct |
13 |
Correct |
15 ms |
12140 KB |
Output is correct |
14 |
Correct |
12 ms |
12140 KB |
Output is correct |
15 |
Correct |
13 ms |
12140 KB |
Output is correct |
16 |
Correct |
12 ms |
12140 KB |
Output is correct |
17 |
Correct |
12 ms |
12140 KB |
Output is correct |
18 |
Correct |
12 ms |
12140 KB |
Output is correct |
19 |
Correct |
12 ms |
12160 KB |
Output is correct |
20 |
Correct |
12 ms |
12140 KB |
Output is correct |
21 |
Correct |
12 ms |
12140 KB |
Output is correct |
22 |
Correct |
14 ms |
12268 KB |
Output is correct |
23 |
Correct |
14 ms |
12268 KB |
Output is correct |
24 |
Correct |
15 ms |
12268 KB |
Output is correct |
25 |
Correct |
14 ms |
12268 KB |
Output is correct |
26 |
Correct |
14 ms |
12268 KB |
Output is correct |
27 |
Correct |
15 ms |
12268 KB |
Output is correct |
28 |
Correct |
14 ms |
12268 KB |
Output is correct |
29 |
Correct |
14 ms |
12268 KB |
Output is correct |
30 |
Correct |
13 ms |
12140 KB |
Output is correct |
31 |
Correct |
17 ms |
12268 KB |
Output is correct |
32 |
Correct |
12 ms |
12140 KB |
Output is correct |
33 |
Correct |
12 ms |
12140 KB |
Output is correct |
34 |
Correct |
12 ms |
12140 KB |
Output is correct |
35 |
Correct |
12 ms |
12140 KB |
Output is correct |
36 |
Correct |
12 ms |
12140 KB |
Output is correct |
37 |
Correct |
13 ms |
12140 KB |
Output is correct |
38 |
Correct |
13 ms |
12268 KB |
Output is correct |
39 |
Correct |
12 ms |
12140 KB |
Output is correct |
40 |
Correct |
12 ms |
12140 KB |
Output is correct |
41 |
Correct |
13 ms |
12140 KB |
Output is correct |
42 |
Correct |
13 ms |
12140 KB |
Output is correct |
43 |
Correct |
13 ms |
12140 KB |
Output is correct |
44 |
Correct |
13 ms |
12140 KB |
Output is correct |
45 |
Correct |
13 ms |
12140 KB |
Output is correct |
46 |
Correct |
13 ms |
12140 KB |
Output is correct |
47 |
Correct |
12 ms |
12128 KB |
Output is correct |
48 |
Correct |
12 ms |
12140 KB |
Output is correct |
49 |
Correct |
14 ms |
12268 KB |
Output is correct |
50 |
Correct |
16 ms |
12140 KB |
Output is correct |
51 |
Correct |
12 ms |
12140 KB |
Output is correct |
52 |
Correct |
13 ms |
12140 KB |
Output is correct |
53 |
Correct |
13 ms |
12140 KB |
Output is correct |
54 |
Correct |
12 ms |
12176 KB |
Output is correct |
55 |
Correct |
13 ms |
12140 KB |
Output is correct |
56 |
Correct |
13 ms |
12140 KB |
Output is correct |
57 |
Correct |
14 ms |
12140 KB |
Output is correct |
58 |
Correct |
14 ms |
12268 KB |
Output is correct |
59 |
Correct |
776 ms |
38796 KB |
Output is correct |
60 |
Correct |
896 ms |
51564 KB |
Output is correct |
61 |
Correct |
12 ms |
12140 KB |
Output is correct |
62 |
Correct |
12 ms |
12140 KB |
Output is correct |
63 |
Correct |
700 ms |
41288 KB |
Output is correct |
64 |
Correct |
16 ms |
12780 KB |
Output is correct |
65 |
Correct |
33 ms |
14700 KB |
Output is correct |
66 |
Correct |
264 ms |
36328 KB |
Output is correct |
67 |
Correct |
744 ms |
57324 KB |
Output is correct |
68 |
Correct |
775 ms |
60312 KB |
Output is correct |
69 |
Correct |
26 ms |
13292 KB |
Output is correct |
70 |
Correct |
205 ms |
24432 KB |
Output is correct |
71 |
Correct |
665 ms |
49876 KB |
Output is correct |
72 |
Correct |
690 ms |
48788 KB |
Output is correct |
73 |
Correct |
200 ms |
22500 KB |
Output is correct |
74 |
Correct |
858 ms |
50272 KB |
Output is correct |
75 |
Correct |
74 ms |
17256 KB |
Output is correct |
76 |
Correct |
762 ms |
62396 KB |
Output is correct |
77 |
Correct |
748 ms |
63364 KB |
Output is correct |
78 |
Correct |
70 ms |
17004 KB |
Output is correct |
79 |
Correct |
757 ms |
54892 KB |
Output is correct |
80 |
Correct |
16 ms |
12396 KB |
Output is correct |
81 |
Correct |
256 ms |
25624 KB |
Output is correct |
82 |
Correct |
814 ms |
51628 KB |
Output is correct |
83 |
Correct |
859 ms |
48992 KB |
Output is correct |
84 |
Correct |
851 ms |
47732 KB |
Output is correct |
85 |
Correct |
847 ms |
49288 KB |
Output is correct |
86 |
Correct |
919 ms |
53768 KB |
Output is correct |
87 |
Correct |
903 ms |
53792 KB |
Output is correct |