#include <stdio.h>
#include <vector>
#include <algorithm>
#include <cassert>
std::vector<int> AdjList[500005];
std::vector<int> Leaf;
int Root;
int H[500005];
int Pa[500005][20];
void dfs(int u, int pa, int h)
{
H[u] = h;
Pa[u][0] = pa;
if (pa == 0)
Root = u;
int i, v, s = AdjList[u].size();
for (i = 0; i < s; i++)
{
v = AdjList[u][i];
if (v != pa)
{
dfs(v, u, h + 1);
}
}
if (s == 1)
Leaf.push_back(u);
}
int cnt;
int M[500005];
int lca(int u, int v)
{
int i;
if (H[v] > H[u])
return lca(v, u);
if (H[u] > H[v])
{
for (i = 19; i >= 0; i--)
{
if (H[Pa[u][i]] > H[v])
u = Pa[u][i];
}
u = Pa[u][0];
}
if (u == v)
return u;
for (i = 19; i >= 0; i--)
{
if (Pa[u][i] != Pa[v][i])
{
u = Pa[u][i];
v = Pa[v][i];
}
}
u = Pa[u][0];
return u;
}
void mark(int u, int v)
{
// printf("mark u%d v%d lca%d\n", u, v, lca(u, v));
M[u]++;
M[v]++;
M[lca(u, v)] -= 2;
}
void dfscheck(int u, int pa)
{
int i, v, s = AdjList[u].size();
for (i = 0; i < s; i++)
{
v = AdjList[u][i];
if (v != pa)
{
dfscheck(v, u);
M[u] += M[v];
}
}
// printf("M[%d] = %d\n", u, M[u]);
assert(M[u] >= 0);
if (M[u] == 0 && pa != 0) cnt++;
}
int N;
int check()
{
int i, j;
for (i = 1; i <= N; i++)
M[i] = 0;
cnt = 0;
for (i = 0, j = Leaf.size() - 1; i < j; i++, j--)
mark(Leaf[i], Leaf[j]);
if (i == j)
mark(Leaf[i], Root);
if (AdjList[1].size() > 1)
dfscheck(1, 0);
else
dfscheck(AdjList[1][0], 0);
return (cnt == 0);
}
int main()
{
scanf("%d", &N);
int i, j, u, v;
for (i = 0; i < N - 1; i++)
{
scanf("%d %d", &u, &v);
AdjList[u].push_back(v);
AdjList[v].push_back(u);
}
if (AdjList[1].size() > 1)
dfs(1, 0, 0);
else
dfs(AdjList[1][0], 0, 0);
for (j = 1; j < 20; j++)
{
for (i = 1; i <= N; i++)
{
Pa[i][j] = Pa[Pa[i][j - 1]][j - 1];
}
}
printf("%d\n", (Leaf.size() + 1)/2);
// if (check())
// {
// for (i = 0, j = Leaf.size() - 1; i < j; i++, j--)
// printf("%d %d\n", Leaf[i], Leaf[j]);
// if (i == j)
// printf("%d %d\n", Leaf[i], Root);
// }
// else
// {
// Leaf.push_back(Leaf[0]);
// Leaf.erase(Leaf.begin());
// if (!check())
// assert(1 == 0);
// for (i = 0, j = Leaf.size() - 1; i < j; i++, j--)
// printf("%d %d\n", Leaf[i], Leaf[j]);
// if (i == j)
// printf("%d %d\n", Leaf[i], Root);
// }
int cnt = 0;
while (!check())
{
if (Leaf.size() < 10)
std::next_permutation(Leaf.begin(), Leaf.end());
else
{
Leaf.push_back(Leaf[0]);
Leaf.erase(Leaf.begin());
}
}
if (cnt == Leaf.size())
assert(1 == 0);
for (i = 0, j = Leaf.size() - 1; i < j; i++, j--)
printf("%d %d\n", Leaf[i], Leaf[j]);
if (i == j)
printf("%d %d\n", Leaf[i], Root);
}
Compilation message
net.cpp: In function 'int main()':
net.cpp:118:39: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
printf("%d\n", (Leaf.size() + 1)/2);
~~~~~~~~~~~~~~~~~~~^
net.cpp:148:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (cnt == Leaf.size())
~~~~^~~~~~~~~~~~~~
net.cpp:99:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
net.cpp:103:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &u, &v);
~~~~~^~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
12024 KB |
Output is correct |
2 |
Correct |
11 ms |
12132 KB |
Output is correct |
3 |
Correct |
11 ms |
12208 KB |
Output is correct |
4 |
Correct |
11 ms |
12208 KB |
Output is correct |
5 |
Correct |
11 ms |
12208 KB |
Output is correct |
6 |
Correct |
12 ms |
12208 KB |
Output is correct |
7 |
Correct |
13 ms |
12244 KB |
Output is correct |
8 |
Correct |
12 ms |
12244 KB |
Output is correct |
9 |
Correct |
15 ms |
12244 KB |
Output is correct |
10 |
Correct |
15 ms |
12244 KB |
Output is correct |
11 |
Correct |
15 ms |
12244 KB |
Output is correct |
12 |
Correct |
12 ms |
12320 KB |
Output is correct |
13 |
Correct |
14 ms |
12320 KB |
Output is correct |
14 |
Correct |
14 ms |
12320 KB |
Output is correct |
15 |
Correct |
12 ms |
12320 KB |
Output is correct |
16 |
Correct |
13 ms |
12320 KB |
Output is correct |
17 |
Correct |
12 ms |
12320 KB |
Output is correct |
18 |
Correct |
12 ms |
12320 KB |
Output is correct |
19 |
Correct |
12 ms |
12320 KB |
Output is correct |
20 |
Correct |
14 ms |
12368 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
12024 KB |
Output is correct |
2 |
Correct |
11 ms |
12132 KB |
Output is correct |
3 |
Correct |
11 ms |
12208 KB |
Output is correct |
4 |
Correct |
11 ms |
12208 KB |
Output is correct |
5 |
Correct |
11 ms |
12208 KB |
Output is correct |
6 |
Correct |
12 ms |
12208 KB |
Output is correct |
7 |
Correct |
13 ms |
12244 KB |
Output is correct |
8 |
Correct |
12 ms |
12244 KB |
Output is correct |
9 |
Correct |
15 ms |
12244 KB |
Output is correct |
10 |
Correct |
15 ms |
12244 KB |
Output is correct |
11 |
Correct |
15 ms |
12244 KB |
Output is correct |
12 |
Correct |
12 ms |
12320 KB |
Output is correct |
13 |
Correct |
14 ms |
12320 KB |
Output is correct |
14 |
Correct |
14 ms |
12320 KB |
Output is correct |
15 |
Correct |
12 ms |
12320 KB |
Output is correct |
16 |
Correct |
13 ms |
12320 KB |
Output is correct |
17 |
Correct |
12 ms |
12320 KB |
Output is correct |
18 |
Correct |
12 ms |
12320 KB |
Output is correct |
19 |
Correct |
12 ms |
12320 KB |
Output is correct |
20 |
Correct |
14 ms |
12368 KB |
Output is correct |
21 |
Correct |
14 ms |
12368 KB |
Output is correct |
22 |
Correct |
17 ms |
12524 KB |
Output is correct |
23 |
Correct |
13 ms |
12524 KB |
Output is correct |
24 |
Correct |
14 ms |
12540 KB |
Output is correct |
25 |
Correct |
13 ms |
12540 KB |
Output is correct |
26 |
Correct |
13 ms |
12556 KB |
Output is correct |
27 |
Correct |
17 ms |
12556 KB |
Output is correct |
28 |
Correct |
14 ms |
12596 KB |
Output is correct |
29 |
Correct |
17 ms |
12596 KB |
Output is correct |
30 |
Correct |
12 ms |
12596 KB |
Output is correct |
31 |
Correct |
14 ms |
12640 KB |
Output is correct |
32 |
Correct |
14 ms |
12640 KB |
Output is correct |
33 |
Correct |
15 ms |
12640 KB |
Output is correct |
34 |
Correct |
12 ms |
12640 KB |
Output is correct |
35 |
Correct |
12 ms |
12640 KB |
Output is correct |
36 |
Correct |
13 ms |
12640 KB |
Output is correct |
37 |
Correct |
13 ms |
12640 KB |
Output is correct |
38 |
Correct |
16 ms |
12640 KB |
Output is correct |
39 |
Correct |
13 ms |
12640 KB |
Output is correct |
40 |
Correct |
12 ms |
12640 KB |
Output is correct |
41 |
Correct |
12 ms |
12640 KB |
Output is correct |
42 |
Correct |
12 ms |
12640 KB |
Output is correct |
43 |
Correct |
13 ms |
12640 KB |
Output is correct |
44 |
Correct |
14 ms |
12640 KB |
Output is correct |
45 |
Correct |
12 ms |
12640 KB |
Output is correct |
46 |
Correct |
14 ms |
12640 KB |
Output is correct |
47 |
Correct |
12 ms |
12640 KB |
Output is correct |
48 |
Correct |
13 ms |
12640 KB |
Output is correct |
49 |
Correct |
13 ms |
12736 KB |
Output is correct |
50 |
Correct |
15 ms |
12736 KB |
Output is correct |
51 |
Correct |
12 ms |
12736 KB |
Output is correct |
52 |
Correct |
12 ms |
12736 KB |
Output is correct |
53 |
Correct |
16 ms |
12768 KB |
Output is correct |
54 |
Correct |
13 ms |
12768 KB |
Output is correct |
55 |
Correct |
13 ms |
12768 KB |
Output is correct |
56 |
Correct |
12 ms |
12768 KB |
Output is correct |
57 |
Correct |
13 ms |
12768 KB |
Output is correct |
58 |
Correct |
16 ms |
12824 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
12024 KB |
Output is correct |
2 |
Correct |
11 ms |
12132 KB |
Output is correct |
3 |
Correct |
11 ms |
12208 KB |
Output is correct |
4 |
Correct |
11 ms |
12208 KB |
Output is correct |
5 |
Correct |
11 ms |
12208 KB |
Output is correct |
6 |
Correct |
12 ms |
12208 KB |
Output is correct |
7 |
Correct |
13 ms |
12244 KB |
Output is correct |
8 |
Correct |
12 ms |
12244 KB |
Output is correct |
9 |
Correct |
15 ms |
12244 KB |
Output is correct |
10 |
Correct |
15 ms |
12244 KB |
Output is correct |
11 |
Correct |
15 ms |
12244 KB |
Output is correct |
12 |
Correct |
12 ms |
12320 KB |
Output is correct |
13 |
Correct |
14 ms |
12320 KB |
Output is correct |
14 |
Correct |
14 ms |
12320 KB |
Output is correct |
15 |
Correct |
12 ms |
12320 KB |
Output is correct |
16 |
Correct |
13 ms |
12320 KB |
Output is correct |
17 |
Correct |
12 ms |
12320 KB |
Output is correct |
18 |
Correct |
12 ms |
12320 KB |
Output is correct |
19 |
Correct |
12 ms |
12320 KB |
Output is correct |
20 |
Correct |
14 ms |
12368 KB |
Output is correct |
21 |
Correct |
14 ms |
12368 KB |
Output is correct |
22 |
Correct |
17 ms |
12524 KB |
Output is correct |
23 |
Correct |
13 ms |
12524 KB |
Output is correct |
24 |
Correct |
14 ms |
12540 KB |
Output is correct |
25 |
Correct |
13 ms |
12540 KB |
Output is correct |
26 |
Correct |
13 ms |
12556 KB |
Output is correct |
27 |
Correct |
17 ms |
12556 KB |
Output is correct |
28 |
Correct |
14 ms |
12596 KB |
Output is correct |
29 |
Correct |
17 ms |
12596 KB |
Output is correct |
30 |
Correct |
12 ms |
12596 KB |
Output is correct |
31 |
Correct |
14 ms |
12640 KB |
Output is correct |
32 |
Correct |
14 ms |
12640 KB |
Output is correct |
33 |
Correct |
15 ms |
12640 KB |
Output is correct |
34 |
Correct |
12 ms |
12640 KB |
Output is correct |
35 |
Correct |
12 ms |
12640 KB |
Output is correct |
36 |
Correct |
13 ms |
12640 KB |
Output is correct |
37 |
Correct |
13 ms |
12640 KB |
Output is correct |
38 |
Correct |
16 ms |
12640 KB |
Output is correct |
39 |
Correct |
13 ms |
12640 KB |
Output is correct |
40 |
Correct |
12 ms |
12640 KB |
Output is correct |
41 |
Correct |
12 ms |
12640 KB |
Output is correct |
42 |
Correct |
12 ms |
12640 KB |
Output is correct |
43 |
Correct |
13 ms |
12640 KB |
Output is correct |
44 |
Correct |
14 ms |
12640 KB |
Output is correct |
45 |
Correct |
12 ms |
12640 KB |
Output is correct |
46 |
Correct |
14 ms |
12640 KB |
Output is correct |
47 |
Correct |
12 ms |
12640 KB |
Output is correct |
48 |
Correct |
13 ms |
12640 KB |
Output is correct |
49 |
Correct |
13 ms |
12736 KB |
Output is correct |
50 |
Correct |
15 ms |
12736 KB |
Output is correct |
51 |
Correct |
12 ms |
12736 KB |
Output is correct |
52 |
Correct |
12 ms |
12736 KB |
Output is correct |
53 |
Correct |
16 ms |
12768 KB |
Output is correct |
54 |
Correct |
13 ms |
12768 KB |
Output is correct |
55 |
Correct |
13 ms |
12768 KB |
Output is correct |
56 |
Correct |
12 ms |
12768 KB |
Output is correct |
57 |
Correct |
13 ms |
12768 KB |
Output is correct |
58 |
Correct |
16 ms |
12824 KB |
Output is correct |
59 |
Correct |
942 ms |
75488 KB |
Output is correct |
60 |
Correct |
1107 ms |
88532 KB |
Output is correct |
61 |
Correct |
13 ms |
88532 KB |
Output is correct |
62 |
Correct |
12 ms |
88532 KB |
Output is correct |
63 |
Correct |
780 ms |
88532 KB |
Output is correct |
64 |
Correct |
18 ms |
88532 KB |
Output is correct |
65 |
Correct |
33 ms |
88532 KB |
Output is correct |
66 |
Correct |
844 ms |
88532 KB |
Output is correct |
67 |
Correct |
1311 ms |
119524 KB |
Output is correct |
68 |
Correct |
1201 ms |
127128 KB |
Output is correct |
69 |
Correct |
24 ms |
127128 KB |
Output is correct |
70 |
Correct |
246 ms |
127128 KB |
Output is correct |
71 |
Correct |
884 ms |
127128 KB |
Output is correct |
72 |
Correct |
849 ms |
127128 KB |
Output is correct |
73 |
Correct |
291 ms |
127128 KB |
Output is correct |
74 |
Correct |
1123 ms |
132024 KB |
Output is correct |
75 |
Correct |
64 ms |
132024 KB |
Output is correct |
76 |
Correct |
894 ms |
143132 KB |
Output is correct |
77 |
Correct |
872 ms |
150000 KB |
Output is correct |
78 |
Correct |
71 ms |
150000 KB |
Output is correct |
79 |
Correct |
1177 ms |
168072 KB |
Output is correct |
80 |
Correct |
16 ms |
168072 KB |
Output is correct |
81 |
Correct |
297 ms |
168072 KB |
Output is correct |
82 |
Correct |
910 ms |
168072 KB |
Output is correct |
83 |
Correct |
1002 ms |
168500 KB |
Output is correct |
84 |
Correct |
1294 ms |
175140 KB |
Output is correct |
85 |
Correct |
954 ms |
181744 KB |
Output is correct |
86 |
Correct |
959 ms |
189548 KB |
Output is correct |
87 |
Correct |
996 ms |
195944 KB |
Output is correct |