#line 1 "a.cpp" // https://qandori.github.io/cp-library/ #include #include using namespace std; using std::cin, std::cout, std::cerr; #define vec vector #if LONG_MAX == 2147483647L #undef long #define long long long #endif #define uint unsigned int #define ulong unsigned long #define overload3(a, b, c, name, ...) name #define rep3(i, a, b) for (int i = (a); i < (b); i++) #define rep2(i, n) rep3(i, 0, n) #define rep1(n) rep2(__i__, n) #define rep(...) overload3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__) #define per3(i, a, b) for (int i = (b) - 1; i >= (a); i--) #define per2(i, n) per3(i, 0, n) #define per1(n) per2(__i__, n) #define per(...) overload3(__VA_ARGS__, per3, per2, per1)(__VA_ARGS__) #define CP_ALL_SELECT(first, ...) first #define CP_ALL_RANGE(a) std::begin(a), std::end(a) #define all(...) CP_ALL_SELECT(__VA_OPT__(CP_ALL_RANGE, ) all)(__VA_ARGS__) #define UNIQUE(a) sort(all(a)), a.erase(unique(all(a)), a.end()), a.shrink_to_fit() #define sz(a) static_cast(a.size()) #ifndef DEBUG #define cerr \ if (false) cerr #undef endl #define endl '\n' #endif inline auto operator^=(vector::reference a, bool b) noexcept { if (b) a.flip(); return a; } inline auto operator&=(vector::reference a, bool b) noexcept { if (!b) a = false; return a; } inline auto operator|=(vector::reference a, bool b) noexcept { if (b) a = true; return a; } inline ostream &operator<<(ostream &os, __int128_t value) { ostream::sentry s(os); if (s) { __uint128_t tmp = value; if (value < 0) tmp = -tmp; char buffer[128]; char *d = std::end(buffer); do { --d; *d = "0123456789"[tmp % 10]; tmp /= 10; } while (tmp != 0); if (value < 0) --d, *d = '-'; const int len = std::end(buffer) - d; if (os.rdbuf()->sputn(d, len) != len) os.setstate(std::ios_base::badbit); } return os; } template ostream &operator<<(ostream &os, pair a) { return os << a.first << ' ' << a.second; }; template ostream &operator<<(ostream &os, vector a) { const int n = a.size(); rep(i, n) { os << a[i]; if (i + 1 != n) os << " "; } return os; } template istream &operator>>(istream &is, pair &a) { return is >> a.first >> a.second; } template ostream &operator<<(ostream &os, array a) { rep(i, n) { os << a[i]; if (i + 1 != n) os << " "; } return os; } template istream &operator>>(istream &is, vector &a) { for (T &i : a) is >> i; return is; } template bool chmin(T &x, S y) { if ((T)y < x) { x = (T)y; return true; } return false; } template bool chmax(T &x, S y) { if (x < (T)y) { x = (T)y; return true; } return false; } template void operator++(vector &a) { for (T &i : a) ++i; } template void operator--(vector &a) { for (T &i : a) --i; } template void operator++(vector &a, int) { for (T &i : a) i++; } template void operator--(vector &a, int) { for (T &i : a) i--; } void init(), solve(); int main() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); cerr << fixed << setprecision(20); init(); int t = 1; // cin >> t; while (t--) solve(); } // #define COMB_MAX 1e6 // #include "lib/math/comb.hpp" // #include "lib/fps/fps.hpp" // #include "lib/math/mint.hpp" void init() {} // 難しくないか?? // 一旦 B スキップ // 手の震えやばいよ〜 // ゲームですねえ // 上に貪欲に進んでいくのが正答っぽい // 毎回愚直にやって間に合うか? // 間に合いそう // 実は lca 以外の情報は切り落とせますね // そっからどうしよう #line 1 "lib/tree/lca.hpp" #line 1 "lib/components/static_range_min.hpp" #line 1 "lib/components/default_init_allocator.hpp" #line 6 "lib/components/default_init_allocator.hpp" template struct DefaultInitAllocator : std::allocator { template struct rebind { using other = DefaultInitAllocator; }; DefaultInitAllocator() = default; template DefaultInitAllocator(const DefaultInitAllocator &) noexcept {} template void construct(U *p) { ::new (static_cast(p)) U; } }; #line 1 "lib/data_structure/sparse_table.hpp" #line 6 "lib/data_structure/sparse_table.hpp" #include #line 11 "lib/data_structure/sparse_table.hpp" #include #line 14 "lib/data_structure/sparse_table.hpp" template class SparseTable { using Value = std::conditional_t, std::uint8_t, S>; using Reference = std::conditional_t, bool, const S &>; int n = 0; std::vector>> data; static decltype(auto) combine(const Value &a, const Value &b) { if constexpr (std::is_same_v || !std::is_invocable_v) return S(op(S(a), S(b))); else return op(a, b); } public: SparseTable() = default; SparseTable(const SparseTable &) = default; SparseTable &operator=(const SparseTable &) = default; SparseTable(SparseTable &&other) noexcept : n(std::exchange(other.n, 0)), data(std::move(other.data)) {} SparseTable &operator=(SparseTable &&other) noexcept { if (this != &other) { n = std::exchange(other.n, 0); data = std::move(other.data); } return *this; } explicit SparseTable(const std::vector &a) { build(a); } void clear() { data.clear(); n = 0; } void build(const std::vector &a) { assert(a.size() <= std::size_t(std::numeric_limits::max())); build(static_cast(a.size()), [&](int i) -> S { return a[i]; }); } template void build(int size, F value) { assert(size >= 0); n = size; data.resize(std::bit_width(unsigned(n))); if (!n) return; if constexpr (std::is_default_constructible_v) { data[0].resize(n); for (int i = 0; i < n; ++i) data[0][i] = value(i); } else { data[0].clear(); data[0].reserve(n); for (int i = 0; i < n; ++i) data[0].push_back(value(i)); } for (int k = 1; k < std::bit_width(unsigned(n)); ++k) { int length = n - (1U << k) + 1, half = 1U << (k - 1); if constexpr (std::is_default_constructible_v) { data[k].resize(length); for (int i = 0; i < length; ++i) data[k][i] = combine(data[k - 1][i], data[k - 1][i + half]); } else { data[k].clear(); data[k].reserve(length); for (int i = 0; i < length; ++i) data[k].push_back(combine(data[k - 1][i], data[k - 1][i + half])); } } } int size() const { return n; } bool empty() const { return n == 0; } Reference operator[](int i) const { assert(0 <= i && i < n); return data[0][i]; } [[gnu::always_inline]] S prod(int l, int r) const { assert(0 <= l && l <= r && r <= n); if constexpr (std::is_same_v) assert(l < r); else if (l == r) return e(); return prod_unchecked(l, r); } [[gnu::always_inline]] S prod_unchecked(int l, int r) const { int k = std::bit_width(unsigned(r - l)) - 1; return combine(data[k][l], data[k][r - (1U << k)]); } S all_prod() const { return prod(0, n); } }; #line 12 "lib/components/static_range_min.hpp" #include #line 16 "lib/components/static_range_min.hpp" template class StaticRangeMin { static T minimum(T a, T b) { return b < a ? b : a; } std::vector values_; std::vector> masks_; SparseTable blocks_; struct Boundaries { std::vector prefix, suffix; }; struct Empty {}; [[no_unique_address]] std::conditional_t boundaries_; T within(int l, int r) const { auto mask = masks_[r - 1] & (~std::uint32_t(0) << (l & 31)); return values_[(l & ~31) + std::countr_zero(mask)]; } public: StaticRangeMin() = default; explicit StaticRangeMin(std::vector values) { build(std::move(values)); } void build(std::vector values) { assert(values.size() <= std::size_t(std::numeric_limits::max())); values_ = std::move(values); int n = size(); masks_.resize(n); for (int first = 0; first < n;) { int last = first + std::min(32, n - first); std::uint32_t mask = 0; for (int i = first; i < last; ++i) { while (mask && !(values_[first + std::bit_width(mask) - 1] < values_[i])) mask &= ~(std::uint32_t(1) << (std::bit_width(mask) - 1)); mask |= std::uint32_t(1) << (i - first); masks_[i] = mask; } first = last; } if constexpr (FastBoundaries) { boundaries_.prefix = values_, boundaries_.suffix = values_; for (int first = 0; first < n;) { int last = first + std::min(32, n - first); for (int i = first + 1; i < last; ++i) boundaries_.prefix[i] = minimum(boundaries_.prefix[i - 1], values_[i]); for (int i = last - 1; i > first; --i) boundaries_.suffix[i - 1] = minimum(values_[i - 1], boundaries_.suffix[i]); first = last; } } blocks_.build(n ? (n - 1) / 32 + 1 : 0, [&](int i) { int last = i * 32 + std::min(32, n - i * 32); if constexpr (FastBoundaries) return T(boundaries_.prefix[last - 1]); else return within(i * 32, last); }); } int size() const { return static_cast(values_.size()); } bool empty() const { return values_.empty(); } std::conditional_t, bool, const T &> operator[](int i) const { assert(0 <= i && i < size()); return values_[i]; } T prod(int l, int r) const { assert(0 <= l && l < r && r <= size()); int a = l / 32, b = (r - 1) / 32; if (a == b) return within(l, r); T value = [&] { if constexpr (FastBoundaries) return minimum(boundaries_.suffix[l], boundaries_.prefix[r - 1]); else return minimum(within(l, (a + 1) * 32), within(b * 32, r)); }(); if (a + 1 < b) value = minimum(value, blocks_.prod_unchecked(a + 1, b)); return value; } std::vector prod_many(std::span> ranges) const { std::vector result; result.reserve(ranges.size()); if constexpr (FastBoundaries) { for (auto [l, r] : ranges) result.emplace_back(prod(l, r)); } else { std::array left, right; for (std::size_t first = 0; first < ranges.size(); first += 32) { int count = int(std::min(32, ranges.size() - first)); auto [sample_l, sample_r] = ranges[first]; assert(0 <= sample_l && sample_l < sample_r && sample_r <= size()); bool wide = std::is_integral_v && sample_r - sample_l >= 256; if (wide) { int a = sample_l / 32, b = (sample_r - 1) / 32; T middle = blocks_.prod_unchecked(a + 1, b); wide = !(blocks_[a] < middle) && !(blocks_[b] < middle); } for (int i = 1; i < count && wide; ++i) wide = ranges[first + i].second - ranges[first + i].first >= 256; if (wide) { for (int i = 0; i < count; ++i) { auto [l, r] = ranges[first + i]; assert(0 <= l && l < r && r <= size()); int a = l / 32, b = (r - 1) / 32; T value = blocks_.prod_unchecked(a + 1, b); if (blocks_[a] < value) value = minimum(value, within(l, (a + 1) * 32)); if (blocks_[b] < value) value = minimum(value, within(b * 32, r)); result.emplace_back(std::move(value)); } continue; } for (int i = 0; i < count; ++i) { auto [l, r] = ranges[first + i]; assert(0 <= l && l < r && r <= size()); int a = l & ~31, b = (r - 1) & ~31; auto mask = masks_[a == b ? r - 1 : a + 31] & (~std::uint32_t(0) << (l & 31)); left[i] = a + std::countr_zero(mask); right[i] = a == b ? left[i] : b + std::countr_zero(masks_[r - 1]); #if defined(__GNUC__) || defined(__clang__) if constexpr (!std::is_same_v) { __builtin_prefetch(values_.data() + left[i]); __builtin_prefetch(values_.data() + right[i]); } #endif } for (int i = 0; i < count; ++i) { auto [l, r] = ranges[first + i]; T value = minimum(values_[left[i]], values_[right[i]]); int a = l / 32 + 1, b = (r - 1) / 32; if (a < b) value = minimum(value, blocks_.prod_unchecked(a, b)); result.emplace_back(std::move(value)); } } } return result; } T all_prod() const { return prod(0, size()); } }; #line 11 "lib/tree/lca.hpp" class LCA { std::vector in, out, order; bool ordered_ = false; StaticRangeMin table; void check([[maybe_unused]] int v) const { assert(0 <= v && v < n && static_cast(in.size()) == n); } template void finish(int root) { in[root] = n; ordered_ = root == 0; for (int i = n - 2; i >= 0; --i) { int v = Ordered ? n - 1 - i : order[i], p = parent[v]; depth[v] = depth[p] + 1; in[v] = in[p]; in[p] -= out[v]; } std::vector values(n); for (int v = 0; v < n; ++v) { --in[v]; out[v] += in[v]; order[in[v]] = v; if constexpr (Ordered) values[in[v]] = v ? parent[v] : 0; else ordered_ &= parent[v] < v; } if constexpr (!Ordered) for (int i = 1; i < n; ++i) values[i] = ordered_ ? parent[order[i]] : in[parent[order[i]]]; table.build(std::move(values)); parent[root] = -1; } public: int n; std::vector> edges; std::vector parent, depth; explicit LCA(int n = 0) : n(n) { assert(0 <= n && n <= std::numeric_limits::max() / 2); edges.reserve(std::max(0, n - 1)); } int add_edge(int u, int v) { assert(0 <= u && u < n && 0 <= v && v < n); edges.emplace_back(u, v); return static_cast(edges.size()) - 1; } void build(int root = 0) { assert(n >= 0 && edges.size() == std::size_t(std::max(0, n - 1))); assert(!n || (0 <= root && root < n)); in.resize(n); out.resize(n); order.resize(n); parent.assign(n, -1); depth.assign(n, 0); table = StaticRangeMin(); if (!n) return; std::vector degree(n), neighbors(n); for (auto [u, v] : edges) { ++degree[u], ++degree[v]; neighbors[u] ^= v, neighbors[v] ^= u; } degree[root] += 2; std::fill(out.begin(), out.end(), 1); int count = 0; for (int v = 0; v < n; ++v) if (degree[v] == 1) order[count++] = v; for (int i = 0; i < count; ++i) { int v = order[i], p = neighbors[v]; parent[v] = p; out[p] += out[v]; neighbors[p] ^= v; if (--degree[p] == 1) order[count++] = p; } assert(count == n - 1); finish(root); } void build_from_parents(std::vector parents) { assert(parents.size() <= std::size_t(std::numeric_limits::max() / 2)); n = static_cast(parents.size()); parent = std::move(parents); in.resize(n); out.assign(n, 1); order.resize(n); depth.assign(n, 0); table = StaticRangeMin(); edges.clear(); edges.reserve(std::max(0, n - 1)); if (!n) return; int root = -1; bool ordered = true; for (int v = 0; v < n; ++v) { int p = parent[v]; assert(-1 <= p && p < n && p != v); if (p == -1) { assert(root == -1); root = v; } else { edges.emplace_back(p, v); ordered &= p < v; } } assert(root != -1); if (ordered) { for (int v = n - 1; v > 0; --v) { out[parent[v]] += out[v]; } finish(root); return; } else { std::fill(in.begin(), in.end(), 0); for (int v = 0; v < n; ++v) if (v != root) ++in[parent[v]]; int count = 0; for (int v = 0; v < n; ++v) if (!in[v] && v != root) order[count++] = v; for (int i = 0; i < count; ++i) { int v = order[i], p = parent[v]; out[p] += out[v]; if (!--in[p] && p != root) order[count++] = p; } assert(count == n - 1); } finish(root); } int lca(int u, int v) const { check(u); check(v); int l = in[u], r = in[v]; if (l == r) return u; if (l > r) std::swap(l, r); ++l; int w = table.prod(l, r + 1); return ordered_ ? w : order[w]; } int dist(int u, int v) const { int w = lca(u, v); return depth[u] + depth[v] - 2 * depth[w]; } int distance(int u, int v) const { return dist(u, v); } bool is_ancestor(int u, int v) const { check(u); check(v); return in[u] <= in[v] && in[v] < out[u]; } std::pair subtree(int v) const { check(v); return {in[v], out[v]}; } }; #line 151 "a.cpp" void solve_() { // 実験を書き始めるのが遅い // 愚直すらバグらせてしまう int n; cin >> n; vec> a(n, vec(n)); auto f = [&](this auto f, int x, int y) -> int { if (x <= y) return a[x][y] = 1; if (y == 0) return a[x][y] = -1; if (a[x][y] != 0) return a[x][y]; const int c = (x - y + 1) / 2; return a[x][y] = -f(y, c); }; rep(i, n) rep(j, n) f(i, j); for (auto &aa : a) { for (int v : aa) cout << (v == 1 ? "#" : "."); cout << endl; } // これ愚直でも間に合う? // 間に合う雰囲気 } void solve() { int n; cin >> n; auto lca = LCA(n); rep(i, n - 1) { int u, v; cin >> u >> v; u--, v--; lca.add_edge(u, v); } lca.build(); int que; cin >> que; auto g = [&](this auto g, int x, int y) -> int { if (x <= y) return 1; if (y == 0) return -1; const int c = (x - y + 1) / 2; return -g(y, c); }; while (que--) { int a, b; cin >> a >> b; a--, b--; const int u = lca.lca(a, b); const int aa = lca.dist(u, a), bb = lca.dist(u, b); // cerr << "! " << aa << " " << bb << endl; cout << (g(aa, bb) == 1 ? "Alice" : "Bob") << endl; } }