#include //#include using namespace std; // using namespace atcoder; // using mint = modint1000000007; // const int mod = 1000000007; // using mint = modint998244353; // const int mod = 998244353; // const int INF = 1e9; // const long long LINF = 1e18; #define rep(i, n) for (int i = 0; i < (n); ++i) #define rep2(i, l, r) for (int i = (l); i < (r); ++i) #define rrep(i, n) for (int i = (n)-1; i >= 0; --i) #define rrep2(i, l, r) for (int i = (r)-1; i >= (l); --i) #define all(x) (x).begin(), (x).end() #define allR(x) (x).rbegin(), (x).rend() #define P pair template inline bool chmax(A& a, const B& b) { if (a < b) { a = b; return true; } return false; } template inline bool chmin(A& a, const B& b) { if (a > b) { a = b; return true; } return false; } /** * @file lca_tree.hpp * @brief LCA を用いた木の処理 * @author kwm_t * @see https://github.com/kwm-t/cp-library/blob/main/tree/lca_tree.hpp */ #ifndef KWM_T_TREE_LCA_TREE_HPP #define KWM_T_TREE_LCA_TREE_HPP #include #include namespace kwm_t::tree { /** * @brief LCA (Binary Lifting) + 距離 + k祖先 + パス判定 * * 典型用途: * - LCA * - 木上の距離 * - k-th ancestor * - パス上判定 / ジャンプ * * 計算量: * - 前処理: O(N log N) * - LCA / k-th ancestor: O(log N) * * verified: * - https://atcoder.jp/contests/awc0059/submissions/75370597 * - https://atcoder.jp/contests/awc0106/submissions/77251198 */ class LcaTree { public: static const int MAXLOGV = 25; int n, root; std::vector> g; std::vector depth; std::vector in, out; std::vector parent[MAXLOGV]; public: LcaTree(std::vector> g, int root = 0) : n((int)g.size()), root(root), g(g) { if (!g.empty())build(); } // LCA int lca(int u, int v) const { if (depth[u] > depth[v]) std::swap(u, v); int diff = depth[v] - depth[u]; for (int k = 0; k < MAXLOGV; k++) { if (diff >> k & 1) { v = parent[k][v]; } } if (u == v) return u; for (int k = MAXLOGV - 1; k >= 0; k--) { if (parent[k][u] != parent[k][v]) { u = parent[k][u]; v = parent[k][v]; } } return parent[0][u]; } // k個上の祖先 int kth_ancestor(int v, int k) const { if (depth[v] < k) return -1; for (int i = 0; i < MAXLOGV; i++) { if (k >> i & 1) { v = parent[i][v]; if (v == -1) return -1; } } return v; } // 距離 int dist(int u, int v) const { int p = lca(u, v); return (depth[u] - depth[p]) + (depth[v] - depth[p]); } // パス上判定 bool on_path(int u, int v, int w) const { return dist(u, w) + dist(v, w) == dist(u, v); } // uからv方向へd進むノード int jump(int u, int v, int d) const { if (d == 0) return u; int uv = dist(u, v); if (uv < d) return -1; int p = lca(u, v); if (p == u) { return kth_ancestor(v, uv - d); } if (p == v) { return kth_ancestor(u, d); } int up = depth[u] - depth[p]; if (up >= d) { return kth_ancestor(u, d); } return kth_ancestor(v, uv - d); } // u→v のパス上の頂点を順番に返す std::vector get_path(int u, int v) const { int p = lca(u, v); std::vector left; std::vector right; // u -> LCA int cur = u; while (cur != p) { left.push_back(cur); cur = parent[0][cur]; } left.push_back(p); // v -> LCA cur = v; while (cur != p) { right.push_back(cur); cur = parent[0][cur]; } std::reverse(right.begin(), right.end()); left.insert(left.end(), right.begin(), right.end()); return left; } private: // 前処理 void build() { depth.resize(n); in.resize(n); out.resize(n); for (int i = 0; i < MAXLOGV; i++) { parent[i].assign(n, -1); } int timer = 0; auto dfs = [&](auto&& self, int v, int p, int d) -> void { in[v] = timer++; parent[0][v] = p; depth[v] = d; for (int to : g[v]) { if (to == p) continue; self(self, to, v, d + 1); } out[v] = timer; }; dfs(dfs, root, -1, 0); for (int k = 0; k + 1 < MAXLOGV; k++) { for (int v = 0; v < n; v++) { if (parent[k][v] < 0) { parent[k + 1][v] = -1; } else { parent[k + 1][v] = parent[k][parent[k][v]]; } } } } }; } // namespace kwm_t::tree #endif // KWM_T_TREE_LCA_TREE_HPP int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n; cin >> n; vector g(n, vector()); rep(i, n - 1) { int u, v; cin >> u >> v; u--, v--; g[u].push_back(v); g[v].push_back(u); } kwm_t::tree::LcaTree lca(g); int q; cin >> q; while (q--) { int u, v; cin >> u >> v; u--, v--; int t = 0; while (u != 0 && v != 0) { t++; int du = lca.dist(u, 0); int dv = lca.dist(v, 0); if (du <= dv) { u = 0; continue; } int d = lca.dist(u, v); d /= 2; u = lca.jump(u, v, d); swap(u, v); } cout << (t % 2 ? "Alice" : "Bob") << endl; } return 0; }