#include <bits/stdc++.h>
using namespace std;
#define rep(i , j , k) for (int i = j; i < k; i++)
#define pb push_back
#define for_all(x) x.begin(),x.end()
typedef long long ll;
typedef pair<int , int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
inline void fileIO(string s) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
template<class T , class S>
inline void smin(T &a, S b) {
if (a > b)
a = b;
}
template<class T , class S>
inline void smax(T &a, S b) {
if (a < b)
a = b;
}
constexpr int N = 1e6 + 10;
int n;
vi adj[N];
vector<pii> res;
pii dp[N];
void dfs(int v, int par = 0) {
vi st;
if (adj[v].size() == 1) {
dp[v] = {v , -1};
return;
}
for (auto e : adj[v])
if (e ^ par) {
dfs(e, v);
if (st.size() > 1) {
res.pb({st.back() , dp[e].first});
st.pop_back();
dp[e].first = -1;
}
if (st.size() > 1 && dp[e].second != -1) {
res.pb({st.back() , dp[e].second});
st.pop_back();
dp[e].second = -1;
}
if (dp[e].first != -1)
st.pb(dp[e].first);
if (dp[e].second != -1)
st.pb(dp[e].second);
}
if (st.size() == 3) {
res.pb({st[0] , st[1]});
int me = st.back();
st.clear();
st.pb(me);
}
dp[v].first = st.back();
st.pop_back();
dp[v].second = st.empty() ? -1 : st.back();
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
rep(i , 1 , n) {
int u , v;
cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
}
rep(i , 1 , n + 1)
if (adj[i].size() > 1) {
dfs(i);
if (dp[i].first != -1 && dp[i].second != -1)
res.pb(dp[i]);
else
res.pb({dp[i].first , i});
break;
}
cout << res.size() << endl;
for (auto e : res)
cout <<e.first << ' ' << e.second << '\n';
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
23780 KB |
Output is correct |
2 |
Correct |
25 ms |
23780 KB |
Output is correct |
3 |
Correct |
24 ms |
23808 KB |
Output is correct |
4 |
Correct |
24 ms |
23808 KB |
Output is correct |
5 |
Correct |
24 ms |
23800 KB |
Output is correct |
6 |
Correct |
25 ms |
23824 KB |
Output is correct |
7 |
Correct |
22 ms |
23808 KB |
Output is correct |
8 |
Correct |
24 ms |
23808 KB |
Output is correct |
9 |
Correct |
26 ms |
23780 KB |
Output is correct |
10 |
Correct |
24 ms |
23860 KB |
Output is correct |
11 |
Correct |
24 ms |
23780 KB |
Output is correct |
12 |
Correct |
26 ms |
23780 KB |
Output is correct |
13 |
Correct |
29 ms |
23800 KB |
Output is correct |
14 |
Correct |
24 ms |
23800 KB |
Output is correct |
15 |
Correct |
27 ms |
23800 KB |
Output is correct |
16 |
Correct |
26 ms |
23808 KB |
Output is correct |
17 |
Correct |
23 ms |
23808 KB |
Output is correct |
18 |
Correct |
24 ms |
23808 KB |
Output is correct |
19 |
Correct |
25 ms |
23800 KB |
Output is correct |
20 |
Correct |
24 ms |
23800 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
23780 KB |
Output is correct |
2 |
Correct |
25 ms |
23780 KB |
Output is correct |
3 |
Correct |
24 ms |
23808 KB |
Output is correct |
4 |
Correct |
24 ms |
23808 KB |
Output is correct |
5 |
Correct |
24 ms |
23800 KB |
Output is correct |
6 |
Correct |
25 ms |
23824 KB |
Output is correct |
7 |
Correct |
22 ms |
23808 KB |
Output is correct |
8 |
Correct |
24 ms |
23808 KB |
Output is correct |
9 |
Correct |
26 ms |
23780 KB |
Output is correct |
10 |
Correct |
24 ms |
23860 KB |
Output is correct |
11 |
Correct |
24 ms |
23780 KB |
Output is correct |
12 |
Correct |
26 ms |
23780 KB |
Output is correct |
13 |
Correct |
29 ms |
23800 KB |
Output is correct |
14 |
Correct |
24 ms |
23800 KB |
Output is correct |
15 |
Correct |
27 ms |
23800 KB |
Output is correct |
16 |
Correct |
26 ms |
23808 KB |
Output is correct |
17 |
Correct |
23 ms |
23808 KB |
Output is correct |
18 |
Correct |
24 ms |
23808 KB |
Output is correct |
19 |
Correct |
25 ms |
23800 KB |
Output is correct |
20 |
Correct |
24 ms |
23800 KB |
Output is correct |
21 |
Correct |
25 ms |
23772 KB |
Output is correct |
22 |
Correct |
25 ms |
23928 KB |
Output is correct |
23 |
Correct |
29 ms |
23928 KB |
Output is correct |
24 |
Correct |
27 ms |
24072 KB |
Output is correct |
25 |
Correct |
25 ms |
23936 KB |
Output is correct |
26 |
Correct |
53 ms |
23928 KB |
Output is correct |
27 |
Correct |
27 ms |
23932 KB |
Output is correct |
28 |
Correct |
25 ms |
23928 KB |
Output is correct |
29 |
Correct |
29 ms |
23944 KB |
Output is correct |
30 |
Correct |
26 ms |
23808 KB |
Output is correct |
31 |
Correct |
29 ms |
23936 KB |
Output is correct |
32 |
Correct |
25 ms |
23808 KB |
Output is correct |
33 |
Correct |
26 ms |
23816 KB |
Output is correct |
34 |
Correct |
26 ms |
23888 KB |
Output is correct |
35 |
Correct |
23 ms |
23800 KB |
Output is correct |
36 |
Correct |
25 ms |
23780 KB |
Output is correct |
37 |
Correct |
25 ms |
23928 KB |
Output is correct |
38 |
Correct |
26 ms |
23936 KB |
Output is correct |
39 |
Correct |
25 ms |
23780 KB |
Output is correct |
40 |
Correct |
25 ms |
23808 KB |
Output is correct |
41 |
Correct |
25 ms |
23808 KB |
Output is correct |
42 |
Correct |
27 ms |
23800 KB |
Output is correct |
43 |
Correct |
30 ms |
23864 KB |
Output is correct |
44 |
Correct |
25 ms |
23808 KB |
Output is correct |
45 |
Correct |
27 ms |
23836 KB |
Output is correct |
46 |
Correct |
25 ms |
23808 KB |
Output is correct |
47 |
Correct |
24 ms |
23808 KB |
Output is correct |
48 |
Correct |
25 ms |
23804 KB |
Output is correct |
49 |
Correct |
24 ms |
23936 KB |
Output is correct |
50 |
Correct |
24 ms |
23800 KB |
Output is correct |
51 |
Correct |
28 ms |
23800 KB |
Output is correct |
52 |
Correct |
27 ms |
24064 KB |
Output is correct |
53 |
Correct |
25 ms |
23876 KB |
Output is correct |
54 |
Correct |
24 ms |
23808 KB |
Output is correct |
55 |
Correct |
24 ms |
23808 KB |
Output is correct |
56 |
Correct |
24 ms |
23856 KB |
Output is correct |
57 |
Correct |
25 ms |
23808 KB |
Output is correct |
58 |
Correct |
24 ms |
23928 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
23780 KB |
Output is correct |
2 |
Correct |
25 ms |
23780 KB |
Output is correct |
3 |
Correct |
24 ms |
23808 KB |
Output is correct |
4 |
Correct |
24 ms |
23808 KB |
Output is correct |
5 |
Correct |
24 ms |
23800 KB |
Output is correct |
6 |
Correct |
25 ms |
23824 KB |
Output is correct |
7 |
Correct |
22 ms |
23808 KB |
Output is correct |
8 |
Correct |
24 ms |
23808 KB |
Output is correct |
9 |
Correct |
26 ms |
23780 KB |
Output is correct |
10 |
Correct |
24 ms |
23860 KB |
Output is correct |
11 |
Correct |
24 ms |
23780 KB |
Output is correct |
12 |
Correct |
26 ms |
23780 KB |
Output is correct |
13 |
Correct |
29 ms |
23800 KB |
Output is correct |
14 |
Correct |
24 ms |
23800 KB |
Output is correct |
15 |
Correct |
27 ms |
23800 KB |
Output is correct |
16 |
Correct |
26 ms |
23808 KB |
Output is correct |
17 |
Correct |
23 ms |
23808 KB |
Output is correct |
18 |
Correct |
24 ms |
23808 KB |
Output is correct |
19 |
Correct |
25 ms |
23800 KB |
Output is correct |
20 |
Correct |
24 ms |
23800 KB |
Output is correct |
21 |
Correct |
25 ms |
23772 KB |
Output is correct |
22 |
Correct |
25 ms |
23928 KB |
Output is correct |
23 |
Correct |
29 ms |
23928 KB |
Output is correct |
24 |
Correct |
27 ms |
24072 KB |
Output is correct |
25 |
Correct |
25 ms |
23936 KB |
Output is correct |
26 |
Correct |
53 ms |
23928 KB |
Output is correct |
27 |
Correct |
27 ms |
23932 KB |
Output is correct |
28 |
Correct |
25 ms |
23928 KB |
Output is correct |
29 |
Correct |
29 ms |
23944 KB |
Output is correct |
30 |
Correct |
26 ms |
23808 KB |
Output is correct |
31 |
Correct |
29 ms |
23936 KB |
Output is correct |
32 |
Correct |
25 ms |
23808 KB |
Output is correct |
33 |
Correct |
26 ms |
23816 KB |
Output is correct |
34 |
Correct |
26 ms |
23888 KB |
Output is correct |
35 |
Correct |
23 ms |
23800 KB |
Output is correct |
36 |
Correct |
25 ms |
23780 KB |
Output is correct |
37 |
Correct |
25 ms |
23928 KB |
Output is correct |
38 |
Correct |
26 ms |
23936 KB |
Output is correct |
39 |
Correct |
25 ms |
23780 KB |
Output is correct |
40 |
Correct |
25 ms |
23808 KB |
Output is correct |
41 |
Correct |
25 ms |
23808 KB |
Output is correct |
42 |
Correct |
27 ms |
23800 KB |
Output is correct |
43 |
Correct |
30 ms |
23864 KB |
Output is correct |
44 |
Correct |
25 ms |
23808 KB |
Output is correct |
45 |
Correct |
27 ms |
23836 KB |
Output is correct |
46 |
Correct |
25 ms |
23808 KB |
Output is correct |
47 |
Correct |
24 ms |
23808 KB |
Output is correct |
48 |
Correct |
25 ms |
23804 KB |
Output is correct |
49 |
Correct |
24 ms |
23936 KB |
Output is correct |
50 |
Correct |
24 ms |
23800 KB |
Output is correct |
51 |
Correct |
28 ms |
23800 KB |
Output is correct |
52 |
Correct |
27 ms |
24064 KB |
Output is correct |
53 |
Correct |
25 ms |
23876 KB |
Output is correct |
54 |
Correct |
24 ms |
23808 KB |
Output is correct |
55 |
Correct |
24 ms |
23808 KB |
Output is correct |
56 |
Correct |
24 ms |
23856 KB |
Output is correct |
57 |
Correct |
25 ms |
23808 KB |
Output is correct |
58 |
Correct |
24 ms |
23928 KB |
Output is correct |
59 |
Correct |
598 ms |
51492 KB |
Output is correct |
60 |
Correct |
662 ms |
54560 KB |
Output is correct |
61 |
Correct |
23 ms |
23800 KB |
Output is correct |
62 |
Correct |
24 ms |
23808 KB |
Output is correct |
63 |
Correct |
454 ms |
48488 KB |
Output is correct |
64 |
Correct |
31 ms |
24568 KB |
Output is correct |
65 |
Correct |
51 ms |
27000 KB |
Output is correct |
66 |
Correct |
260 ms |
51752 KB |
Output is correct |
67 |
Correct |
769 ms |
79484 KB |
Output is correct |
68 |
Correct |
751 ms |
80720 KB |
Output is correct |
69 |
Correct |
32 ms |
24824 KB |
Output is correct |
70 |
Correct |
162 ms |
34436 KB |
Output is correct |
71 |
Correct |
448 ms |
57696 KB |
Output is correct |
72 |
Correct |
405 ms |
56416 KB |
Output is correct |
73 |
Correct |
171 ms |
31988 KB |
Output is correct |
74 |
Correct |
653 ms |
53484 KB |
Output is correct |
75 |
Correct |
81 ms |
27512 KB |
Output is correct |
76 |
Correct |
416 ms |
57216 KB |
Output is correct |
77 |
Correct |
424 ms |
57364 KB |
Output is correct |
78 |
Correct |
65 ms |
29048 KB |
Output is correct |
79 |
Correct |
717 ms |
75464 KB |
Output is correct |
80 |
Correct |
29 ms |
24064 KB |
Output is correct |
81 |
Correct |
170 ms |
34412 KB |
Output is correct |
82 |
Correct |
617 ms |
55232 KB |
Output is correct |
83 |
Correct |
656 ms |
53468 KB |
Output is correct |
84 |
Correct |
663 ms |
53380 KB |
Output is correct |
85 |
Correct |
676 ms |
53492 KB |
Output is correct |
86 |
Correct |
621 ms |
54412 KB |
Output is correct |
87 |
Correct |
609 ms |
54420 KB |
Output is correct |