-
Notifications
You must be signed in to change notification settings - Fork 185
/
f.cc
110 lines (106 loc) · 2.26 KB
/
f.cc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
// https://codeforces.com/contest/1228/problem/A
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using si = unordered_set<int>;
using vsi = vector<si>;
using vvi = vector<vi>;
using qi = queue<int>;
int n, k, r, s = -1;
vi d, depth;
vsi h;
vvi g;
bool dfs(int u, int p) {
if (p == -1 && (d[u] != 2 && d[u] != 3)) return 0;
if (p == -1 && d[u] == 3) {
if (r) return 0;
r = u + 1;
int c = 0;
for (int v : g[u]) {
if (depth[v] == depth[u] - 1) s = v + 1;
else if (depth[v] == depth[u] - 2) c++;
}
if (c != 2 || s == -1) return 0;
}
if (p >= 0 && d[u] == 4 && depth[u] > 1) {
if (r) return 0;
r = u + 1;
}
if (p >= 0 && d[u] == 2 && depth[u] > 1) return 0;
if (p >= 0 && d[u] == 2 && depth[u] == 1) {
if (r) return 0;
r = u + 1;
}
bool ok = 1;
for (int v : g[u])
if (v != p) {
if (r != u + 1 && depth[v] + 1 != depth[u]) ok = 0;
if (!dfs(v, u)) ok = 0;
}
return ok;
}
int main() {
int n, u, v;
cin >> n;
if (n == 2) {
cout << "2\n1 2\n";
return 0;
}
int k = 1;
for (int i = 0; i < n; i++) k *= 2;
k -= 2;
g = vvi(k), h = vsi(k);
for (int i = 0; i < k - 1; i++) {
cin >> u >> v;
u--, v--;
g[u].push_back(v);
g[v].push_back(u);
h[u].insert(v);
h[v].insert(u);
}
vi c(5);
d = vi(k), depth = vi(k);
qi q;
for (int i = 0; i < k; i++) {
d[i] = g[i].size();
if (d[i] >= 1 && d[i] <= 4) c[d[i]]++;
else c[0]++;
if (d[i] == 1) {
q.push(i);
depth[i] = 0;
}
}
int l = (k + 2) / 2;
if (c[0] || c[4] > 1 || (c[1] != l && c[1] != l - 1)) {
cout << "0\n";
return 0;
}
vi p(k, -1);
while (!q.empty()) {
int u = q.front();
q.pop();
if (h[u].empty()) continue;
int v = *h[u].begin();
p[u] = v;
depth[v] = max(depth[u], depth[u] + 1);
h[v].erase(u);
if (h[v].size() == 1) q.push(v);
}
int root = -1;
for (int i = 0; i < k; i++)
if (p[i] == -1) {
if (root == -1) root = i;
else {
cout << "0\n";
return 0;
}
}
if (root == -1) {
cout << "0\n";
return 0;
}
if (dfs(root, -1)) {
if (s >= 0) cout << "2\n" << min(r, s) << " " << max(r, s) << "\n";
else cout << "1\n" << r << "\n";
} else cout << "0\n";
}