#include #include #include using namespace std; template class monoidontree { int n, bit; std::vector>> g; std::vector dubu[20], dubd[20]; std::vector dub[20], dep; bool isbuild; T e; F eval; public: monoidontree(int num, T E, F func) : e(E), eval(func), n(num), g(num), dep(num, num + 1), isbuild(false) { for (bit = 0; (1 << bit) < n; ++bit); ++bit; for (int i = 0; i < bit; ++i) { dub[i].assign(n, -1); dubu[i].assign(n, e); dubd[i].assign(n, e); } } void add_edge(int u, int v, T val) {g[u].emplace_back(v, val);} void build() { if (isbuild) return; isbuild = true; std::vector st; dep[0] = 0; for (st.push_back(0); !st.empty();) { int now = st.back(); st.pop_back(); for (auto [to, v] : g[now]) { if (dep[to] > dep[now] + 1) { dep[to] = dep[now] + 1; dub[0][to] = now; dubd[0][to] = v; st.push_back(to); } } } for (int i = 0; i < n; ++i) { for (auto [to, v] : g[i]) { if (to == dub[0][i]) { dubu[0][i] = v; break; } } } for (int i = 1; i < bit; ++i) { for (int j = 0; j < n; ++j) { if (dub[i - 1][j] == -1) continue; dub[i][j] = dub[i - 1][dub[i - 1][j]]; if (dub[i][j] != -1) { dubu[i][j] = eval(dubu[i - 1][j], dubu[i - 1][dub[i - 1][j]]); dubd[i][j] = eval(dubd[i - 1][dub[i - 1][j]], dubd[i - 1][j]); } } } } T getval(int s, int t) { if (!isbuild) { isbuild = true; build(); } int ds = dep[s], dt = dep[t]; T ansu = e, ansd = e; if (ds > dt) { int d = ds - dt; for (int i = 0; i < bit && d > 0; ++i) { if (d & (1 << i)) { ansu = eval(ansu, dubu[i][s]); s = dub[i][s]; d ^= (1 << i); } } } else if (ds < dt) { int d = dt - ds; for (int i = 0; i < bit && d > 0; ++i) { if (d & (1 << i)) { ansd = eval(dubd[i][t], ansd); t = dub[i][t]; d ^= (1 << i); } } } for (int i = bit - 1; i >= 0; --i) { if (dub[i][s] == dub[i][t]) continue; ansu = eval(ansu, dubu[i][s]); ansd = eval(dubu[i][t], ansd); s = dub[i][s]; t = dub[i][t]; } if (s != t) { ansu = eval(ansu, dubu[0][s]); ansd = eval(dubd[0][t], ansd); } return eval(ansu, ansd); } int getlca(int s, int t) { if (!isbuild) { isbuild = true; build(); } if (s == t) return s; int ds = dep[s], dt = dep[t]; if (ds > dt) { int d = ds - dt; for (int i = 0; i < bit && d > 0; ++i) { if (d & (1 << i)) { s = dub[i][s]; d ^= (1 << i); } } } else if (ds < dt) { int d = dt - ds; for (int i = 0; i < bit && d > 0; ++i) { if (d & (1 << i)) { t = dub[i][t]; d ^= (1 << i); } } } for (int i = bit - 1; i >= 0; --i) { if (dub[i][s] == dub[i][t]) continue; s = dub[i][s]; t = dub[i][t]; } if (s != t) s = dub[0][s]; return s; } }; template monoidontree(int, T, F) -> monoidontree; int main() { int n; cin >> n; vector> g(n); monoidontree mot(n, 0, [](int a, int b) -> int {return a + b;}); for (int i = 1; i < n; ++i) { int u, v; cin >> u >> v; --u, --v; mot.add_edge(u, v, 1); mot.add_edge(v, u, 1); } mot.build(); int q; cin >> q; while (q--) { int a, b; cin >> a >> b; --a, --b; int lab = mot.getlca(a, b), la1 = mot.getlca(0, a), lb1 = mot.getlca(0, b); int rot = lab ^ la1 ^ lb1; if (rot == a) { cout << "Alice" << endl; continue; } else if (rot == b) { cout << "Bob" << endl; continue; } int da = mot.getval(rot, a), db = mot.getval(rot, b); int l = 0, r = da + db, m = da, now = 0; while (true) { if (now == 0) { if (abs(m - l) <= abs(r - m)) { cout << "Alice" << endl; break; } l = (l + r) / 2; } else { if (abs(m - l) >= abs(r - m)) { cout << "Bob" << endl; break; } r = (l + r + 1) / 2; } now ^= 1; } } }