#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define FOR(i, a, b) for(int (i) = (a); (i) < (b); ++(i)) #define rFOR(i, a, b) for(int (i) = (b); (i) >= (a); --(i)) #define REP(i, n) FOR(i, 0, n) #define rREP(i, n) rFOR(i, 0, (n-1)) #define SORT(A) std::sort((A).begin(), (A).end()) #define ALL(A) (A).begin(), (A).end() // 座標圧縮 (for vector) : ソートしてから使うのが一般的 ; SORT(A) => COORDINATE_COMPRESSION(A) #define COORDINATE_COMPRESSION(A) (A).erase(unique((A).begin(),(A).end()),(A).end()) using lli = long long int; using pii = std::pair; // グリッド上の縦横移動 constexpr std::array, 4> dxdy = { std::pair( 1, 0), std::pair(-1, 0), std::pair( 0, 1), std::pair( 0, -1) }; void VintOut(std::vector& A){ const int n = A.size(); if(n == 0){putchar('\n'); return;} printf("%d", A[0]); for(int i = 1; i < n; ++i) printf(" %d", A[i]); putchar('\n'); } void VintOut(std::vector& A){ const int n = A.size(); if(n == 0){ putchar('\n'); return;} printf("%lld", A[0]); for(int i = 1; i < n; ++i) printf(" %lld", A[i]); putchar('\n'); } template inline bool chmin(T& a, T b){ if(b < a){ a = b; return true;} return false; } template inline bool chmax(T& a, T b){ if(a < b){ a = b; return true;} return false; } inline bool isIn(int x, int y, int H, int W){ return 0 <= x and x < H and 0 <= y and y < W; } inline bool bitUP(int state, int k){ return (state >> k) & 1; } inline bool bitUP(long long int state, int k){ return (state >> k) & 1;} // z-algorithm template std::vector z_algorithm(const T &str) { const int n = str.size(); std::vector resOfCP(n); resOfCP[0] = n; int i = 1, j = 0; while (i < n) { while (i + j < n and str[j] == str[i + j]) ++j; resOfCP[i] = j; if (j == 0) { ++i; continue;} int k = 1; while (i + k < n and k + resOfCP[k] < j) resOfCP[i + k] = resOfCP[k], ++k; i += k; j -= k; } return resOfCP; } // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ constexpr int N = 1e5; std::bitset P; std::vector> E; // UnionFind木構造 : 0-indexed | 0, 1, ..., n-1 class UnionFindTree{ private: int n; // 要素数 int numberOfSets; // 集合の数 std::vector Parent; // 親のノード std::vector Size; // 属する集合の大きさ public: // コンストラクタ UnionFindTree(int n):n(n), numberOfSets(n){ Size.assign(n, 1); Parent.resize(n); for(int i = 0; i < n; ++i) Parent[i] = i; } // 集合の大きさを変更する関数 void resize(int sz){ n = sz; numberOfSets = n; Size.assign(n, 1); Parent.resize(n); for(int i = 0; i < n; ++i) Parent[i] = i; } // 頂点 vertex の属する根を返す int rootOf(int vertex){ // 根が自分自身ならば終了 if(Parent[vertex] == vertex) return vertex; // そうでないなら, 親を属する集合の根に付け替える return Parent[vertex] = rootOf(Parent[vertex]); } // 頂点 x, y を併合する : すでに x, yが同じ集合に属しているなら false を返す bool unite(int x, int y){ int root_x = rootOf(x); int root_y = rootOf(y); if(root_x == root_y) return false; if(Size[root_x] < Size[root_y]) std::swap(root_x, root_y); Parent[root_y] = root_x; Size[root_x] += Size[root_y]; numberOfSets--; return true; } // 頂点 x, y が同じ集合に属しているかを判定する関数 inline bool sameSet(int x, int y){ return rootOf(x) == rootOf(y); } // 属している集合の要素数を返す関数 inline int setSize(int vertex){ return Size[rootOf(vertex)]; } // 集合の数を返す inline int getNumberOfSets(void) const { return numberOfSets; } }; int main(void){ int n; scanf("%d", &n); UnionFindTree UFT(n); E.assign(n, std::vector(0)); for(int i = 1; i < n; ++i){ int u, v; scanf("%d%d", &u, &v); E[u].push_back(v); E[v].push_back(u); UFT.unite(u, v); } bool flag = false; if(UFT.getNumberOfSets() == 1) flag = true; else if(UFT.getNumberOfSets() == 2){ int root; for(root = 0; root < n; ++root) if(UFT.setSize(root) == n - 1) break; if(root == n) goto OUT; int lsize = 0; std::vector dist(n, -1); dist[0] = 0; std::stack> Stk; Stk.emplace(root, -1); while(not Stk.empty()){ int v, pv; std::tie(v, pv) = Stk.top(); Stk.pop(); for(int nv : E[v]){ if(dist[nv] == -1){ dist[nv] = dist[v] + 1; Stk.emplace(nv, v); } else if(nv != pv){ int d = dist[v] + dist[nv] + 1; if(lsize < d) lsize = d; } } } flag = (lsize + 1 == n); } OUT: if(flag) puts("Bob"); else puts("Alice"); return 0; }