#line 2 "library/template/template.hpp" // repo: https://github.com/kumacs/library-cpp // docs: https://kumacs.github.io/library-cpp #include using namespace std; #line 2 "library/template/macro.hpp" #define rep(i, a, b) for (int i = (a); i < (int)(b); i++) #define rrep(i, a, b) for (int i = (int)(b) - 1; i >= (a); i--) #define ALL(v) (v).begin(), (v).end() #define UNIQUE(v) sort(ALL(v)), (v).erase(unique(ALL(v)), (v).end()) #define SZ(v) (int)v.size() #define MIN(v) *min_element(ALL(v)) #define MAX(v) *max_element(ALL(v)) #define LB(v, x) int(lower_bound(ALL(v), (x)) - (v).begin()) #define UB(v, x) int(upper_bound(ALL(v), (x)) - (v).begin()) #define YN(b) cout << ((b) ? "YES" : "NO") << "\n"; #define Yn(b) cout << ((b) ? "Yes" : "No") << "\n"; #define yn(b) cout << ((b) ? "yes" : "no") << "\n"; #line 10 "library/template/template.hpp" #line 2 "library/template/util.hpp" using uint = unsigned int; using ll = long long int; using ull = unsigned long long; using i128 = __int128_t; using u128 = __uint128_t; template using priority_queue_asc = priority_queue, greater>; template S SUM(const vector& a) { return accumulate(ALL(a), S(0)); } template inline bool chmin(T1& a, T2 b) { if (a > b) { a = b; return true; } return false; } template inline bool chmax(T1& a, T2 b) { if (a < b) { a = b; return true; } return false; } template inline bool chmin_opt(optional& a, T2 b) { if (!a || a > b) { a = b; return true; } return false; } template inline bool chmax_opt(optional& a, T2 b) { if (!a || a < b) { a = b; return true; } return false; } template int popcnt(T x) { return __builtin_popcountll(x); } template int topbit(T x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); } template int lowbit(T x) { return (x == 0 ? -1 : __builtin_ctzll(x)); } #line 12 "library/template/template.hpp" #line 2 "library/template/inout.hpp" struct Fast { Fast() { cin.tie(nullptr); ios_base::sync_with_stdio(false); cout << fixed << setprecision(15); } } fast; ostream& operator<<(ostream& os, __uint128_t x) { char buf[40]; size_t k = 0; while (x > 0) buf[k++] = (char)(x % 10 + '0'), x /= 10; if (k == 0) buf[k++] = '0'; while (k) os << buf[--k]; return os; } ostream& operator<<(ostream& os, __int128_t x) { return x < 0 ? (os << '-' << (__uint128_t)(-x)) : (os << (__uint128_t)x); } template ostream& operator<<(ostream& os, const array& a); template istream& operator>>(istream& is, pair& p) { return is >> p.first >> p.second; } template ostream& operator<<(ostream& os, const pair& p) { return os << p.first << " " << p.second; } template istream& operator>>(istream& is, vector& a) { for (auto& v : a) is >> v; return is; } template ostream& operator<<(ostream& os, const vector& a) { for (auto it = a.begin(); it != a.end();) { os << *it; if (++it != a.end()) os << " "; } return os; } template ostream& operator<<(ostream& os, const array& a) { for (auto it = a.begin(); it != a.end();) { os << *it; if (++it != a.end()) os << " "; } return os; } template ostream& operator<<(ostream& os, const set& st) { os << "{"; for (auto it = st.begin(); it != st.end();) { os << *it; if (++it != st.end()) os << ","; } os << "}"; return os; } template ostream& operator<<(ostream& os, const map& mp) { os << "{"; for (auto it = mp.begin(); it != mp.end();) { os << it->first << ":" << it->second; if (++it != mp.end()) os << ","; } os << "}"; return os; } void in() {} template void in(T& t, U&... u) { cin >> t; in(u...); } template void in_zip(int n, T&... t) { assert(n >= 0 && ((size(t) >= static_cast(n)) && ...)); for (int i = 0; i < n; i++) in(t[i]...); } void out() { cout << "\n"; } template void out(const T& t, const U&... u) { cout << t; if (sizeof...(u)) cout << sep; out(u...); } template void out_opt(const optional& opt, const U& fallback, ostream& os = cout) { if (opt.has_value()) os << opt.value(); else os << fallback; os << "\n"; } template void out_opt(const vector>& vec, const U& fallback, ostream& os = cout) { for (auto it = vec.begin(); it != vec.end();) { if ((*it).has_value()) os << (*it).value(); else os << fallback; if (++it != vec.end()) os << " "; } os << "\n"; } namespace IO { template T read(U&&... u) { T t = T(forward(u)...); in(t); return t; } namespace Graph { vector> unweighted(int n, int m, bool directed = false, int offset = 1) { vector> g(n); for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; u -= offset, v -= offset; g[u].push_back(v); if (!directed) g[v].push_back(u); } return g; } template vector>> weighted(int n, int m, bool directed = false, int offset = 1) { vector>> g(n); for (int i = 0; i < m; i++) { int u, v; T w; cin >> u >> v >> w; u -= offset, v -= offset; g[u].push_back({v, w}); if (!directed) g[v].push_back({u, w}); } return g; } } // namespace Graph namespace Tree { vector> unweighted(int n, bool directed = false, int offset = 1) { return Graph::unweighted(n, n - 1, directed, offset); } template vector>> weighted(int n, bool directed = false, int offset = 1) { return Graph::weighted(n, n - 1, directed, offset); } vector> rooted(int n, bool to_root = true, bool to_leaf = true, int offset = 1) { vector> g(n); for (int i = 1; i < n; i++) { int p; cin >> p; p -= offset; if (to_root) g[i].push_back(p); if (to_leaf) g[p].push_back(i); } return g; } } // namespace Tree } // namespace IO #line 14 "library/template/template.hpp" #line 2 "library/template/debug.hpp" #ifdef LOCAL #define debug 1 #define show(...) _show(0, #__VA_ARGS__, __VA_ARGS__) #else #define debug 0 #define show(...) true #endif template void _show(int, T) { cerr << '\n'; } template void _show(int i, const T1& a, const T2& b, const T3&... c) { for (; a[i] != ',' && a[i] != '\0'; i++) cerr << a[i]; cerr << ":" << b << " "; _show(i + 1, a, c...); } #line 2 "main.cpp" #line 2 "library/graph/graph.hpp" template struct GraphBase { public: GraphBase() : GraphBase(0) {} GraphBase(int size) : n(size) { assert(size >= 0); g.resize(size); } size_t size() const { return n; } const vector& operator[](int x) const { assert(0 <= x && x < n); return g[x]; } vector& operator[](int x) { assert(0 <= x && x < n); return g[x]; } protected: int n; vector> g; }; struct EdgeUnweighted { int to; }; struct GraphUnweighted : GraphBase { using base = GraphBase; public: GraphUnweighted() : base(0) {} GraphUnweighted(int size) : base(size) {} GraphUnweighted(const vector>& graph) : base(graph.size()) { for (int x = 0; x < n; x++) { base::g[x].reserve(graph[x].size()); for (int y : graph[x]) base::g[x].push_back({y}); } } void add_edge(int x, int y) { (*this)[x].push_back({y}); (*this)[y].push_back({x}); } void add_edge_directed(int from, int to) { (*this)[from].push_back({to}); } }; struct EdgeUnweightedIndexed { int to, id; }; struct GraphUnweightedIndexed : GraphBase { using base = GraphBase; public: GraphUnweightedIndexed() : GraphUnweightedIndexed(0) {} GraphUnweightedIndexed(int size) : base(size), m(0) {} int edge_count() const { return m; } int add_edge(int x, int y) { int id = m++; (*this)[x].push_back({y, id}); (*this)[y].push_back({x, id}); return id; } int add_edge_directed(int from, int to) { int id = m++; (*this)[from].push_back({to, id}); return id; } private: int m; }; template struct EdgeWeighted { int to; T weight; }; template struct GraphWeighted : GraphBase> { using base = GraphBase>; public: GraphWeighted() : base(0) {} GraphWeighted(int size) : base(size) {} GraphWeighted(const vector>>& graph) : base(graph.size()) { for (int x = 0; x < base::n; x++) { base::g[x].reserve(graph[x].size()); for (const auto& [y, w] : graph[x]) base::g[x].push_back({y, w}); } } void add_edge(int x, int y, T w) { (*this)[x].push_back({y, w}); (*this)[y].push_back({x, w}); } void add_edge_directed(int from, int to, T w) { (*this)[from].push_back({to, w}); } }; inline GraphWeighted GraphUnweightedToWeighted(const GraphUnweighted& g) { GraphWeighted h(g.size()); for (int x = 0; x < static_cast(g.size()); x++) { h[x].reserve(g[x].size()); for (const auto& e : g[x]) h[x].push_back({e.to, 1}); } return h; } /** * @brief Graph * @docs docs/graph/graph.md */ #line 2 "library/data-structure/sparse-table.hpp" #line 2 "library/algebraic-structure/util.hpp" #ifdef __cpp_concepts #define REQUIRES(...) requires __VA_ARGS__ #else #define REQUIRES(...) #endif #line 3 "library/algebraic-structure/magma.hpp" #ifdef __cpp_concepts template concept Magma = requires(typename M::value_type x, typename M::value_type y) { typename M::value_type; { M::op(x, y) } -> same_as; }; #endif template struct AddMagma { using value_type = T; static T op(T x, T y) { return x + y; } }; template struct MulMagma { using value_type = T; static T op(T x, T y) { return x * y; } }; template struct MaxMagma { using value_type = T; static T op(T x, T y) { return x > y ? x : y; } }; template struct MinMagma { using value_type = T; static T op(T x, T y) { return x < y ? x : y; } }; #line 4 "library/data-structure/sparse-table.hpp" template REQUIRES(Magma) struct SparseTable { using T = typename M::value_type; private: int n; vector> st; public: SparseTable() : n(0) {} SparseTable(const vector& arr) { n = arr.size(); int log = 1; while (n >> log) log++; st = vector>(log); st[0] = vector(arr.begin(), arr.end()); for (int k = 1; k < log; k++) { const auto& stp = st[k - 1]; auto sti = vector(n - (1 << k) + 1); for (int i = 0; i < (int)sti.size(); i++) sti[i] = M::op(stp[i], stp[i + (1 << (k - 1))]); st[k] = move(sti); } } T prod(int l, int r) const // [l,r) { assert(0 <= l && l < r && r <= n); int j = bit_width(static_cast(r - l)) - 1; return M::op(st[j][l], st[j][r - (1 << j)]); } }; /** * @brief Sparse Table * @docs docs/data-structure/sparse-table.md */ #line 3 "library/tree/lowest-common-ancestor.hpp" struct LowestCommonAncestor { using P = pair; struct LcaMagma { using value_type = P; static P op(P x, P y) { return x.second <= y.second ? x : y; } }; protected: int n, r; SparseTable st; vector in_time, depth, parent, euler_tour; public: size_t size() const { return n; } int root() const { return r; } LowestCommonAncestor() : n(0), r(0) {} template LowestCommonAncestor(const G& g, int root = 0) { build(g, root); } template void build(const G& g, int root = 0) { n = g.size(), r = root; assert(n > 0); assert(0 <= r && r < n); parent.assign(n, -1); depth.assign(n, 0); in_time.assign(n, 0); euler_tour.clear(); euler_tour.reserve(2 * n - 1); { stack dfs; dfs.push(r); vector idx(n); while (!dfs.empty()) { int x = dfs.top(); dfs.pop(); if (idx[x] == 0) in_time[x] = euler_tour.size(); euler_tour.push_back(x); if (idx[x] < static_cast(g[x].size())) { dfs.push(x); int y = g[x][idx[x]++].to; if (y != parent[x]) { parent[y] = x; depth[y] = depth[x] + 1; dfs.push(y); } } } } vector

data; data.reserve(euler_tour.size()); for (auto v : euler_tour) data.push_back({v, depth[v]}); st = SparseTable(data); } int lca(int u, int v) const { assert(0 <= u && u < n); assert(0 <= v && v < n); int x = in_time[u], y = in_time[v]; if (x > y) swap(x, y); return st.prod(x, y + 1).first; } }; /** * @brief Lowest Common Ancestor * @docs docs/tree/lowest-common-ancestor.md */ #line 5 "main.cpp" void solve() { int N; in(N); auto G = IO::Tree::unweighted(N); vector d(N, N); d[0] = 0; queue qu; qu.push(0); while (!qu.empty()) { int x = qu.front(); qu.pop(); for (auto y : G[x]) if (chmin(d[y], d[x] + 1)) qu.push(y); } GraphUnweighted g(G); LowestCommonAncestor lca(g); int Q; in(Q); rep(_, 0, Q) { int A, B; in(A, B); A--, B--; int z = d[lca.lca(A, B)]; int x = d[A] - z, y = d[B] - z; while (x > 0 && y > 0) { x = max(0, x - (x + y) / 2); if (x == 0) break; y = max(0, y - (x + y) / 2); } out(x == 0 ? "Alice" : "Bob"); } } int main() { int T = 1; // in(T); while (T--) solve(); }