/* IN THE NAME OF GOD */
/* |\/| /-\ |\| | |\/| /-\ */
#include "bits/stdc++.h"
using namespace std;
#define sz(x) (int)x.size()
#define endl '\n'
#define pb push_back
#define all(x) x.begin(), x.end()
#define F first
#define S second
#define mr make_pair
//#define int long long
#define pii pair<int, int>
typedef long double ld;
typedef long long ll;
const int N = 5e5 + 10;
const ll MOD = 1e9 + 7;
const int inf = 1e9;
const ll INF = 1e18;
vector<int> g[N];
int l[N], L, par[N], root;
set<int> le, st[N];
void dfs(int v, int p){
for(int u : g[v]){
if(u == p)
continue;
dfs(u, v);
par[u] = v;
l[v] += l[u];
}
if(sz(g[v]) == 1){
l[v]++;
L++;
le.insert(v);
}
}
void dfs2(int v){
for(int u : g[v]){
if(u == par[v])
continue;
dfs2(u);
if(v == root)
continue;
if(sz(st[v]) < sz(st[u]))
st[v].swap(st[u]);
for(int y : st[u])
st[v].insert(y);
st[u].clear();
}
if(sz(g[v]) == 1){
st[v].insert(v);
le.erase(v);
}
}
int32_t main(){
ios_base:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
cin >> n;
int u, v;
for(int i = 1; i < n; i++){
cin >> u >> v;
g[u].pb(v);
g[v].pb(u);
}
dfs(1, 0);
int mx = 0, sm;
for(int i = 1; i <= n; i++){
mx = 0, sm = 0;
for(int u : g[i]){
if(u == par[i])
continue;
mx = max(mx, l[u]);
sm += l[u];
}
mx = max(mx, L - sm);
if(mx <= L / 2 && sz(g[i]) >= 2){
root = i;
break;
}
}
if(root == 0)
cout << 2/0;
dfs2(root);
st[0] = le;
l[0] = sz(st[0]);
set<pii> nomily_cheat_nazan;
for(int u : g[root]){
if(u == par[root])
continue;
nomily_cheat_nazan.insert(mr(l[u], u));
}
if(sz(st[0]) != 0)
nomily_cheat_nazan.insert(mr(sz(st[0]), 0));
cout << L / 2 + (L % 2 != 0) << endl;
while(sz(nomily_cheat_nazan) > 1){
//cout << "$" << sz(nomily_cheat_nazan) << endl;
auto it = nomily_cheat_nazan.end();
auto it2 = it;
it--;
it2--;
it2--;
l[it->S]--;
l[it2->S]--;
//cout << "#" << it->S << " " << it2->S << endl;
cout << *st[it2->S].begin() << " " << *st[it->S].begin() << endl;
st[it->S].erase(*st[it->S].begin());
st[it2->S].erase(*st[it2->S].begin());
if(l[it->S] > 0)
nomily_cheat_nazan.insert(mr(l[it->S], it->S));
if(l[it2->S] > 0)
nomily_cheat_nazan.insert(mr(l[it2->S], it2->S));
nomily_cheat_nazan.erase(it);
nomily_cheat_nazan.erase(it2);
//cout << "!" << sz(nomily_cheat_nazan) << endl;
}
if(nomily_cheat_nazan.empty())
return 0;
int w = *st[nomily_cheat_nazan.begin()->S].begin(), W;
if(par[w] == root || par[root] == w){
if(root == 1 && w == 2)
W = 3;
else if(root == 2 && w == 1)
W = 3;
else if(root == 1)
W = 2;
else if(root == 2)
W = 1;
else if(w == 1)
W = 2;
else if(w == 2)
W = 1;
else
W = 3;
}
else
W = root;
cout << w << " " << W;
}
Compilation message
net.cpp: In function 'int32_t main()':
net.cpp:89:12: warning: division by zero [-Wdiv-by-zero]
89 | cout << 2/0;
| ~^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
17 ms |
35540 KB |
Output is correct |
2 |
Correct |
17 ms |
35540 KB |
Output is correct |
3 |
Correct |
18 ms |
35556 KB |
Output is correct |
4 |
Correct |
18 ms |
35444 KB |
Output is correct |
5 |
Correct |
21 ms |
35540 KB |
Output is correct |
6 |
Correct |
18 ms |
35540 KB |
Output is correct |
7 |
Correct |
17 ms |
35552 KB |
Output is correct |
8 |
Correct |
17 ms |
35560 KB |
Output is correct |
9 |
Correct |
19 ms |
35540 KB |
Output is correct |
10 |
Correct |
17 ms |
35524 KB |
Output is correct |
11 |
Correct |
17 ms |
35540 KB |
Output is correct |
12 |
Correct |
20 ms |
35540 KB |
Output is correct |
13 |
Correct |
18 ms |
35508 KB |
Output is correct |
14 |
Correct |
17 ms |
35500 KB |
Output is correct |
15 |
Correct |
19 ms |
35540 KB |
Output is correct |
16 |
Correct |
18 ms |
35556 KB |
Output is correct |
17 |
Correct |
19 ms |
35540 KB |
Output is correct |
18 |
Correct |
18 ms |
35540 KB |
Output is correct |
19 |
Correct |
17 ms |
35448 KB |
Output is correct |
20 |
Correct |
20 ms |
35504 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
17 ms |
35540 KB |
Output is correct |
2 |
Correct |
17 ms |
35540 KB |
Output is correct |
3 |
Correct |
18 ms |
35556 KB |
Output is correct |
4 |
Correct |
18 ms |
35444 KB |
Output is correct |
5 |
Correct |
21 ms |
35540 KB |
Output is correct |
6 |
Correct |
18 ms |
35540 KB |
Output is correct |
7 |
Correct |
17 ms |
35552 KB |
Output is correct |
8 |
Correct |
17 ms |
35560 KB |
Output is correct |
9 |
Correct |
19 ms |
35540 KB |
Output is correct |
10 |
Correct |
17 ms |
35524 KB |
Output is correct |
11 |
Correct |
17 ms |
35540 KB |
Output is correct |
12 |
Correct |
20 ms |
35540 KB |
Output is correct |
13 |
Correct |
18 ms |
35508 KB |
Output is correct |
14 |
Correct |
17 ms |
35500 KB |
Output is correct |
15 |
Correct |
19 ms |
35540 KB |
Output is correct |
16 |
Correct |
18 ms |
35556 KB |
Output is correct |
17 |
Correct |
19 ms |
35540 KB |
Output is correct |
18 |
Correct |
18 ms |
35540 KB |
Output is correct |
19 |
Correct |
17 ms |
35448 KB |
Output is correct |
20 |
Correct |
20 ms |
35504 KB |
Output is correct |
21 |
Correct |
17 ms |
35556 KB |
Output is correct |
22 |
Correct |
21 ms |
35820 KB |
Output is correct |
23 |
Correct |
18 ms |
35796 KB |
Output is correct |
24 |
Correct |
19 ms |
35796 KB |
Output is correct |
25 |
Correct |
18 ms |
35620 KB |
Output is correct |
26 |
Correct |
18 ms |
35664 KB |
Output is correct |
27 |
Correct |
19 ms |
35620 KB |
Output is correct |
28 |
Correct |
19 ms |
35716 KB |
Output is correct |
29 |
Correct |
19 ms |
35668 KB |
Output is correct |
30 |
Correct |
18 ms |
35540 KB |
Output is correct |
31 |
Correct |
18 ms |
35668 KB |
Output is correct |
32 |
Correct |
17 ms |
35540 KB |
Output is correct |
33 |
Correct |
18 ms |
35556 KB |
Output is correct |
34 |
Correct |
17 ms |
35480 KB |
Output is correct |
35 |
Correct |
17 ms |
35540 KB |
Output is correct |
36 |
Correct |
17 ms |
35540 KB |
Output is correct |
37 |
Correct |
17 ms |
35496 KB |
Output is correct |
38 |
Correct |
17 ms |
35540 KB |
Output is correct |
39 |
Correct |
18 ms |
35484 KB |
Output is correct |
40 |
Correct |
17 ms |
35444 KB |
Output is correct |
41 |
Correct |
18 ms |
35540 KB |
Output is correct |
42 |
Correct |
19 ms |
35540 KB |
Output is correct |
43 |
Correct |
18 ms |
35668 KB |
Output is correct |
44 |
Correct |
17 ms |
35548 KB |
Output is correct |
45 |
Correct |
17 ms |
35540 KB |
Output is correct |
46 |
Correct |
18 ms |
35540 KB |
Output is correct |
47 |
Correct |
18 ms |
35444 KB |
Output is correct |
48 |
Correct |
19 ms |
35580 KB |
Output is correct |
49 |
Correct |
19 ms |
35668 KB |
Output is correct |
50 |
Correct |
17 ms |
35548 KB |
Output is correct |
51 |
Correct |
19 ms |
35532 KB |
Output is correct |
52 |
Correct |
17 ms |
35572 KB |
Output is correct |
53 |
Correct |
17 ms |
35540 KB |
Output is correct |
54 |
Correct |
19 ms |
35552 KB |
Output is correct |
55 |
Correct |
17 ms |
35540 KB |
Output is correct |
56 |
Correct |
17 ms |
35484 KB |
Output is correct |
57 |
Correct |
18 ms |
35540 KB |
Output is correct |
58 |
Correct |
18 ms |
35668 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
17 ms |
35540 KB |
Output is correct |
2 |
Correct |
17 ms |
35540 KB |
Output is correct |
3 |
Correct |
18 ms |
35556 KB |
Output is correct |
4 |
Correct |
18 ms |
35444 KB |
Output is correct |
5 |
Correct |
21 ms |
35540 KB |
Output is correct |
6 |
Correct |
18 ms |
35540 KB |
Output is correct |
7 |
Correct |
17 ms |
35552 KB |
Output is correct |
8 |
Correct |
17 ms |
35560 KB |
Output is correct |
9 |
Correct |
19 ms |
35540 KB |
Output is correct |
10 |
Correct |
17 ms |
35524 KB |
Output is correct |
11 |
Correct |
17 ms |
35540 KB |
Output is correct |
12 |
Correct |
20 ms |
35540 KB |
Output is correct |
13 |
Correct |
18 ms |
35508 KB |
Output is correct |
14 |
Correct |
17 ms |
35500 KB |
Output is correct |
15 |
Correct |
19 ms |
35540 KB |
Output is correct |
16 |
Correct |
18 ms |
35556 KB |
Output is correct |
17 |
Correct |
19 ms |
35540 KB |
Output is correct |
18 |
Correct |
18 ms |
35540 KB |
Output is correct |
19 |
Correct |
17 ms |
35448 KB |
Output is correct |
20 |
Correct |
20 ms |
35504 KB |
Output is correct |
21 |
Correct |
17 ms |
35556 KB |
Output is correct |
22 |
Correct |
21 ms |
35820 KB |
Output is correct |
23 |
Correct |
18 ms |
35796 KB |
Output is correct |
24 |
Correct |
19 ms |
35796 KB |
Output is correct |
25 |
Correct |
18 ms |
35620 KB |
Output is correct |
26 |
Correct |
18 ms |
35664 KB |
Output is correct |
27 |
Correct |
19 ms |
35620 KB |
Output is correct |
28 |
Correct |
19 ms |
35716 KB |
Output is correct |
29 |
Correct |
19 ms |
35668 KB |
Output is correct |
30 |
Correct |
18 ms |
35540 KB |
Output is correct |
31 |
Correct |
18 ms |
35668 KB |
Output is correct |
32 |
Correct |
17 ms |
35540 KB |
Output is correct |
33 |
Correct |
18 ms |
35556 KB |
Output is correct |
34 |
Correct |
17 ms |
35480 KB |
Output is correct |
35 |
Correct |
17 ms |
35540 KB |
Output is correct |
36 |
Correct |
17 ms |
35540 KB |
Output is correct |
37 |
Correct |
17 ms |
35496 KB |
Output is correct |
38 |
Correct |
17 ms |
35540 KB |
Output is correct |
39 |
Correct |
18 ms |
35484 KB |
Output is correct |
40 |
Correct |
17 ms |
35444 KB |
Output is correct |
41 |
Correct |
18 ms |
35540 KB |
Output is correct |
42 |
Correct |
19 ms |
35540 KB |
Output is correct |
43 |
Correct |
18 ms |
35668 KB |
Output is correct |
44 |
Correct |
17 ms |
35548 KB |
Output is correct |
45 |
Correct |
17 ms |
35540 KB |
Output is correct |
46 |
Correct |
18 ms |
35540 KB |
Output is correct |
47 |
Correct |
18 ms |
35444 KB |
Output is correct |
48 |
Correct |
19 ms |
35580 KB |
Output is correct |
49 |
Correct |
19 ms |
35668 KB |
Output is correct |
50 |
Correct |
17 ms |
35548 KB |
Output is correct |
51 |
Correct |
19 ms |
35532 KB |
Output is correct |
52 |
Correct |
17 ms |
35572 KB |
Output is correct |
53 |
Correct |
17 ms |
35540 KB |
Output is correct |
54 |
Correct |
19 ms |
35552 KB |
Output is correct |
55 |
Correct |
17 ms |
35540 KB |
Output is correct |
56 |
Correct |
17 ms |
35484 KB |
Output is correct |
57 |
Correct |
18 ms |
35540 KB |
Output is correct |
58 |
Correct |
18 ms |
35668 KB |
Output is correct |
59 |
Correct |
862 ms |
76848 KB |
Output is correct |
60 |
Correct |
1053 ms |
77004 KB |
Output is correct |
61 |
Correct |
18 ms |
35540 KB |
Output is correct |
62 |
Correct |
17 ms |
35460 KB |
Output is correct |
63 |
Correct |
763 ms |
72404 KB |
Output is correct |
64 |
Correct |
19 ms |
36052 KB |
Output is correct |
65 |
Correct |
26 ms |
38232 KB |
Output is correct |
66 |
Correct |
142 ms |
56084 KB |
Output is correct |
67 |
Correct |
564 ms |
92832 KB |
Output is correct |
68 |
Correct |
545 ms |
90980 KB |
Output is correct |
69 |
Correct |
32 ms |
37580 KB |
Output is correct |
70 |
Correct |
255 ms |
56460 KB |
Output is correct |
71 |
Correct |
1215 ms |
107432 KB |
Output is correct |
72 |
Correct |
1149 ms |
102104 KB |
Output is correct |
73 |
Correct |
160 ms |
46284 KB |
Output is correct |
74 |
Correct |
858 ms |
72556 KB |
Output is correct |
75 |
Correct |
66 ms |
42940 KB |
Output is correct |
76 |
Correct |
1212 ms |
93992 KB |
Output is correct |
77 |
Correct |
1214 ms |
95664 KB |
Output is correct |
78 |
Correct |
62 ms |
40600 KB |
Output is correct |
79 |
Correct |
559 ms |
78480 KB |
Output is correct |
80 |
Correct |
25 ms |
35976 KB |
Output is correct |
81 |
Correct |
216 ms |
55212 KB |
Output is correct |
82 |
Correct |
955 ms |
94084 KB |
Output is correct |
83 |
Correct |
872 ms |
71404 KB |
Output is correct |
84 |
Correct |
816 ms |
73720 KB |
Output is correct |
85 |
Correct |
916 ms |
71404 KB |
Output is correct |
86 |
Correct |
1036 ms |
77352 KB |
Output is correct |
87 |
Correct |
1010 ms |
78332 KB |
Output is correct |