#line 1 "f.cpp" // https://github.com/potato167/po167_library #include #line 4 "f.cpp" using namespace std; using ll=long long; const ll ILL=2167167167167167167; const int INF=2100000000; #define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++) #define all(p) p.begin(),p.end() template using pq_ = priority_queue, greater>; template int LB(vector &v,T a){return lower_bound(v.begin(),v.end(),a)-v.begin();} template int UB(vector &v,T a){return upper_bound(v.begin(),v.end(),a)-v.begin();} template bool chmin(T &a,T b){if(b bool chmax(T &a,T b){if(a void So(vector &v) {sort(v.begin(),v.end());} template void Sore(vector &v) {sort(v.begin(),v.end(),[](T x,T y){return x>y;});} bool yneos(bool a,bool upp=false){if(a){cout<<(upp?"YES\n":"Yes\n");}else{cout<<(upp?"NO\n":"No\n");}return a;} template void vec_out(vector &p,int ty=0){ if(ty==2){cout<<'{';for(int i=0;i<(int)p.size();i++){if(i){cout<<",";}cout<<'"'< T vec_min(vector &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmin(ans,x);return ans;} template T vec_max(vector &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmax(ans,x);return ans;} template T vec_sum(vector &a){T ans=T(0);for(auto &x:a) ans+=x;return ans;} int pop_count(long long a){int res=0;while(a){res+=(int)(a&1),a>>=1;}return res;} template T square(T a){return a * a;} #line 4 "/Users/Shared/po167_library/ds/Sparse_table.hpp" namespace po167{ template struct Sparse_table{ int n; int depth; std::vector> val; void init(std::vector &v){ depth = 1; n = v.size(); while ((1 << depth) <= n) depth++; val.resize(depth); val[0] = v; for (int i = 1; i < depth; i++){ val[i].resize(n); for (int j = 0; j <= n - (1 << i); j++){ val[i][j] = op(val[i - 1][j], val[i - 1][j + (1 << (i - 1))]); } } } Sparse_table(std::vector v){ init(v); } Sparse_table(){} // 0 <= l < r <= n // if l == r : assert T prod(int l, int r){ assert(0 <= l && l < r && r <= n); int z=31-__builtin_clz(r-l); return op(val[z][l], val[z][r - (1 << z)]); } }; } #line 6 "/Users/Shared/po167_library/graph/tree/LCA.hpp" namespace po167{ int op(int a, int b){ return std::min(a, b); } struct LCA{ Sparse_table table; std::vector depth; std::vector E; std::vector order; int var_num; void init(std::vector> &g, int root = 0){ var_num = g.size(); assert(0 <= root && root < var_num); std::vector val; depth.assign(var_num, -1); depth[root] = 0; E.resize(var_num); std::vector tmp; order.clear(); tmp.reserve(var_num); order.reserve(var_num); int c = 0; auto dfs = [&](auto self, int var, int pare) -> void { E[var] = c++; if (var != root) tmp.push_back(E[pare]); order.push_back(var); for (auto x : g[var]) if (depth[x] == -1){ depth[x] = depth[var] + 1; self(self, x, var); } }; dfs(dfs, root, -1); assert(c == var_num); table.init(tmp); } void init(std::vector &pare){ int root = -1; int n = pare.size(); std::vector> g(n); for (int i = 0; i < n; i++){ if (pare[i] < 0){ assert(root == -1); root = i; } else{ assert(0 <= pare[i] && pare[i] < n); g[pare[i]].push_back(i); } } assert(root != -1); init(g, root); } LCA (std::vector> g, int root = 0){ init(g, root); } LCA (std::vector pare){ init(pare); } LCA(){ } int lca(int a, int b){ assert(0 <= std::min(a, b) && std::max(a, b) < var_num); if (a == b) return a; if (E[a] > E[b]) std::swap(a, b); return order[table.prod(E[a], E[b])]; } int dist(int a, int b){ assert(0 <= std::min(a, b) && std::max(a, b) < var_num); return depth[a] + depth[b] - 2 * depth[lca(a, b)]; } int back(int var, int len){ assert(len <= depth[var]); if (len == 0) return var; int l = 0, r = E[var]; while (r - l > 1){ int m = (l + r) / 2; if (depth[var] - depth[order[table.prod(m, E[var])]] < len){ r = m; } else l = m; } return order[table.prod(l, E[var])]; } // a -> b int jump(int a, int b, int len){ int c = lca(a, b); if (len <= depth[a] - depth[c]) return back(a, len); len -= depth[a] - depth[c]; if (len <= depth[b] - depth[c]) return back(b, depth[b] - depth[c] - len); return -1; } }; } #line 28 "f.cpp" void solve(); // DEAR MYSTERIES / TOMOO int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t = 1; // cin >> t; rep(i, 0, t) solve(); } void solve(){ int N; cin >> N; vector> G(N); rep(i, 0, N - 1) { int a, b; cin >> a >> b; a--, b--; G[a].push_back(b); G[b].push_back(a); } po167::LCA L(G); int Q; cin >> Q; while (Q--) { int a, b; cin >> a >> b; a--, b--; int c = L.lca(a, b); int d1 = L.dist(a, c); int d2 = L.dist(b, c); int t = 0; while (true) { if (d1 <= d2) { break; } d1 -= (d1 + d2) / 2; swap(d1, d2); t ^= 1; } cout << (t ? "Bob\n" : "Alice\n"); } }