#include #include #include #include #include #include #include using namespace std; using ll = long long; struct Graph { struct Vertex { int n, f; }; struct Edge { int i, n; }; Graph(int n, int m) : v(n, { -1 }), e(m), n(n), m(0) {} void add_edge(int i, int j) { e[m] = { j, v[i].n }; v[i].n = m; m++; } void dfs(int i, int p, int d) { if (v[i].f) return; else v[i].f = 1; int k = 0; for (int j = v[i].n; j >= 0; j = e[j].n) { Edge &o = e[j]; k++; if (o.i == p) continue; dfs(o.i, i, d + 1); } l = min(l, k); } void solve() { int x = 0; int p[2]; for (int i = 0; i < n; i++) { if (v[i].f) continue; l = 2; dfs(i, -1, 0); if (x < 2) { p[x] = l; } x++; } int b; if (x < 2) { b = 1; } else if (x > 2) { b = 0; } else { if (p[0] == 1 || p[1] == 1) b = 0; else b = 1; } cout << (b == 0 ? "Alice" : "Bob") << endl; } vector v; vector e; int n, m; int l; }; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; Graph g(n, (n - 1) * 2); for (int i = 0; i < n - 1; i++) { int a, b; cin >> a >> b; g.add_edge(a, b); g.add_edge(b, a); } g.solve(); //連結成分が1個のときは爆破したところを直せばいい //3個以上のときは無理 //2個のとき、連結成分を増やせるかが勝負 常になもりと木か? //ただし木の側が辺を持ってないと ただの閉路というのもある return 0; }