// SPDX-License-Identifier: CC0-1.0 // // [English] // To the extent possible under law, the author(s) have dedicated all copyright // and related and neighboring rights to this software to the public domain // worldwide. This software is distributed without any warranty. // See for details. // // [日本語] // 法律上可能な範囲で、著作者はこのソフトウェアに関する著作権および // 著作隣接権を含むすべての関連する権利を、全世界でパブリックドメインに // 提供しています。本ソフトウェアは一切の保証なく配布されます。 // 自由にコピー・改変・再配布・商用利用できます(クレジット表記は不要です)。 // 詳細は を参照してください。 // ※ 英語の文面および CC0 1.0 の正式な条文(英語)が優先されます。 #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll=long long; #include using mint=atcoder::modint998244353; ostream& operator<<(ostream& os,const mint& x){ os<>(istream& is,mint& x){ int t; is>>t; x=t; return is; } template ostream& operator<<(ostream& os,const pair& p); template istream& operator>>(istream& is,pair& p); template ostream& operator<<(ostream& os,const array& arr); template istream& operator>>(istream& is,array& arr); template ostream& operator<<(ostream& os,const vector& vec); template istream& operator>>(istream& is,vector& vec); template ostream& operator<<(ostream& os,const pair& p){ os< istream& operator>>(istream& is,pair& p){ is>>p.first>>p.second; return is; } template ostream& operator<<(ostream& os,const array& arr){ for(int i=0;i istream& operator>>(istream& is,array& arr){ for(int i=0;i>arr[i]; return is; } template ostream& operator<<(ostream& os,const vector& vec){ for(int i=0;i<(int)vec.size();i++)os< istream& operator>>(istream& is,vector& vec){ for(int i=0;i<(int)vec.size();i++)is>>vec[i]; return is; } template void input_vec(Vecs&... vs) { const auto n = get<0>(tie(vs...)).size(); for (size_t i = 0; i < n; ++i) ((cin >> vs[i]), ...); } template void output_vec(const Vecs&... vs) { const auto n = get<0>(tie(vs...)).size(); for (size_t i = 0; i < n; ++i) { bool first = true; (((cout << (exchange(first, false) ? "" : " ") << vs[i])), ...); cout << endl; } } template C make_unique(C vec){ ranges::sort(vec); vec.erase(unique(vec.begin(),vec.end()),vec.end()); return vec; } vector Iota(int n,int s=0){ vector res(n); iota(res.begin(),res.end(),s); return res; } vector Iotall(int n,ll s=0){ vector res(n); iota(res.begin(),res.end(),s); return res; } void YESNO(bool f){ if(f)cout<<"Yes"<; using vvl=vector>; using vvvl=vector>>; using vi=vector; using vvi=vector>; using vvvi=vector>>; using vmi=vector; using vvmi=vector>; using vvvmi=vector>>; //https://atcoder.jp/contests/awc0150/submissions/79608947 // generated by ChatGPT outside of contest time. #include #include #include template struct disjoint_sparse_table { public: disjoint_sparse_table() : disjoint_sparse_table(0) {} explicit disjoint_sparse_table(int n) : disjoint_sparse_table(std::vector(n, e())) {} explicit disjoint_sparse_table(const std::vector& v) : _n((int)v.size()), data_(v) { log_ = 0; while ((1LL << log_) < _n) ++log_; table_.assign(log_, std::vector(_n, e())); for (int k = 0; k < log_; ++k) { const long long half = 1LL << k; const long long block = half << 1; for (long long l = 0; l < _n; l += block) { const int m = (int)std::min(l + half, _n); const int r = (int)std::min(l + block, _n); // 左半分: suffix if ((int)l < m) { table_[k][m - 1] = data_[m - 1]; for (int i = m - 2; i >= (int)l; --i) { table_[k][i] = op(data_[i], table_[k][i + 1]); } } // 右半分: prefix if (m < r) { table_[k][m] = data_[m]; for (int i = m + 1; i < r; ++i) { table_[k][i] = op(table_[k][i - 1], data_[i]); } } } } } S get(int p) const { assert(0 <= p && p < _n); return data_[p]; } S prod(int l, int r) const { assert(0 <= l && l <= r && r <= _n); if (l == r) return e(); if (l + 1 == r) return data_[l]; const unsigned x = static_cast(l ^ (r - 1)); const int k = 31 - __builtin_clz(x); return op(table_[k][l], table_[k][r - 1]); } S all_prod() const { return prod(0, _n); } template int max_right(int l) const { return max_right(l, f); } template int max_right(int l, F f) const { assert(0 <= l && l <= _n); assert(f(e())); if (l == _n) return _n; if (f(prod(l, _n))) return _n; int ok = l; int ng = _n; while (ng - ok > 1) { const int m = ok + (ng - ok) / 2; if (f(prod(l, m))) { ok = m; } else { ng = m; } } return ok; } template int min_left(int r) const { return min_left(r, f); } template int min_left(int r, F f) const { assert(0 <= r && r <= _n); assert(f(e())); if (r == 0) return 0; if (f(prod(0, r))) return 0; int ng = 0; int ok = r; while (ok - ng > 1) { const int m = ng + (ok - ng) / 2; if (f(prod(m, r))) { ok = m; } else { ng = m; } } return ok; } private: int _n; int log_; std::vector data_; std::vector> table_; }; //https://atcoder.jp/contests/awc0150/submissions/79608947 // generated by ChatGPT outside of contest time. #include #include #include #include #include namespace tree_lca_detail { using rmq_value = std::pair; // {depth, vertex} inline rmq_value rmq_op(rmq_value a, rmq_value b) { return std::min(a, b); } inline rmq_value rmq_e() { return { std::numeric_limits::max(), std::numeric_limits::max() }; } } // namespace tree_lca_detail class tree_lca { using rmq_value = tree_lca_detail::rmq_value; using dst_type = disjoint_sparse_table< rmq_value, tree_lca_detail::rmq_op, tree_lca_detail::rmq_e>; public: struct auxiliary_tree { struct edge { int to; long long length; }; // Auxiliary Tree 上での根 int root = -1; // 無向隣接リスト std::vector> graph; // compressed vertex -> original vertex // // 元の頂点番号の昇順になっている。 std::vector vertex; // root を根としたときの親 std::vector parent; // parent との辺の長さ std::vector parent_edge_length; // 元々 make_auxiliary_tree() に渡された頂点なら true std::vector is_terminal; int size() const { return (int)vertex.size(); } int original_vertex(int v) const { assert(0 <= v && v < size()); return vertex[v]; } /* * original vertex -> compressed vertex * * Auxiliary Tree に含まれなければ -1 * * O(log |V_aux|) */ int compressed_id(int v) const { auto it = std::lower_bound(vertex.begin(), vertex.end(), v); if (it == vertex.end() || *it != v) { return -1; } return (int)(it - vertex.begin()); } }; explicit tree_lca( const std::vector>& graph, int root = 0 ) : n_((int)graph.size()), root_(root), depth_(n_), first_(n_, -1), parent_(n_, -1) { assert(n_ > 0); assert(0 <= root_ && root_ < n_); /* * Euler Tour * * tour[i] = {depth, vertex} * * 再帰 DFS を避けている。 */ std::vector tour; tour.reserve(2 * n_ - 1); struct frame { int v; int p; int next; }; std::vector stack; stack.reserve(n_); depth_[root_] = 0; parent_[root_] = -1; first_[root_] = 0; tour.push_back({0, root_}); stack.push_back({root_, -1, 0}); while (!stack.empty()) { frame& f = stack.back(); // v の全ての子を処理し終えた if (f.next == (int)graph[f.v].size()) { stack.pop_back(); // 親へ戻る if (!stack.empty()) { int p = stack.back().v; tour.push_back({depth_[p], p}); } continue; } int to = graph[f.v][f.next++]; if (to == f.p) continue; parent_[to] = f.v; depth_[to] = depth_[f.v] + 1; first_[to] = (int)tour.size(); tour.push_back({depth_[to], to}); stack.push_back({to, f.v, 0}); } rmq_ = dst_type(tour); } template explicit tree_lca( const std::vector>>& graph, int root = 0 ) : n_((int)graph.size()), root_(root), depth_(n_), first_(n_, -1), parent_(n_, -1) { assert(n_ > 0); assert(0 <= root_ && root_ < n_); /* * Euler Tour * * tour[i] = {depth, vertex} * * 再帰 DFS を避けている。 */ std::vector tour; tour.reserve(2 * n_ - 1); struct frame { int v; int p; int next; }; std::vector stack; stack.reserve(n_); depth_[root_] = 0; parent_[root_] = -1; first_[root_] = 0; tour.push_back({0, root_}); stack.push_back({root_, -1, 0}); while (!stack.empty()) { frame& f = stack.back(); // v の全ての子を処理し終えた if (f.next == (int)graph[f.v].size()) { stack.pop_back(); // 親へ戻る if (!stack.empty()) { int p = stack.back().v; tour.push_back({depth_[p], p}); } continue; } int to = graph[f.v][f.next++].second; if (to == f.p) continue; parent_[to] = f.v; depth_[to] = depth_[f.v] + graph[f.v][f.next-1].first; first_[to] = (int)tour.size(); tour.push_back({depth_[to], to}); stack.push_back({to, f.v, 0}); } rmq_ = dst_type(tour); } int size() const { return n_; } int root() const { return root_; } /* * 根から v までの距離 = depth * * O(1) */ long long depth(int v) const { assert(0 <= v && v < n_); return depth_[v]; } /* * 元の木での親 * * root なら -1 * * O(1) */ int parent(int v) const { assert(0 <= v && v < n_); return parent_[v]; } /* * Lowest Common Ancestor * * O(1) */ int lca(int u, int v) const { assert(0 <= u && u < n_); assert(0 <= v && v < n_); int l = first_[u]; int r = first_[v]; if (l > r) std::swap(l, r); return rmq_.prod(l, r + 1).second; } /* * 2頂点間の距離 * * O(1) */ long long dist(int u, int v) const { int w = lca(u, v); return depth_[u] + depth_[v] - 2 * depth_[w]; } /* * 与えられた頂点集合を含む Auxiliary Tree を構築する。 * * https://smijake3.hatenablog.com/entry/2019/09/15/200200#%E3%82%BD%E3%83%BC%E3%83%882%E5%9B%9E%E3%81%AE%E6%96%B9%E6%B3%95 * の「ソート1回の方法」。 * * k := distinct な入力頂点数 * * 時間計算量: * O(k log k) * * Auxiliary Tree の頂点数: * <= 2k - 1 * * 入力 vs はコピーして処理するので、呼び出し側の vector は変更しない。 */ auxiliary_tree make_auxiliary_tree( std::vector vs ) const { auxiliary_tree res; if (vs.empty()) { return res; } for (int v : vs) { assert(0 <= v && v < n_); } /* * preorder 順にソート。 * * first_[v] は Euler Tour における最初の出現位置なので * preorder 順序と一致する。 */ std::sort( vs.begin(), vs.end(), [&](int u, int v) { return first_[u] < first_[v]; } ); /* * first_ は各頂点で異なるので、 * preorder 順でも同一頂点は隣接する。 */ vs.erase( std::unique(vs.begin(), vs.end()), vs.end() ); const int k = (int)vs.size(); /* * stack: * 現在処理している部分の祖先列。 * * 全て元の木の頂点番号で管理する。 */ std::vector stack; stack.reserve(2 * k); /* * Auxiliary Tree に出現した頂点。 * * この時点ではソートされていない。 */ std::vector aux_vertices; aux_vertices.reserve(2 * k); /* * Auxiliary Tree の有向辺 * * {parent, child} * * いずれも元の木における頂点番号。 */ std::vector> edges; edges.reserve(2 * k); stack.push_back(vs[0]); aux_vertices.push_back(vs[0]); /* * 「ソート1回の方法」の本体。 */ for (int i = 0; i + 1 < k; ++i) { const int w = lca(vs[i], vs[i + 1]); if (w != vs[i]) { int last = stack.back(); stack.pop_back(); while ( !stack.empty() && depth_[w] < depth_[stack.back()] ) { edges.emplace_back( stack.back(), last ); last = stack.back(); stack.pop_back(); } if ( stack.empty() || stack.back() != w ) { stack.push_back(w); aux_vertices.push_back(w); edges.emplace_back(w, last); } else { edges.emplace_back(w, last); } } stack.push_back(vs[i + 1]); aux_vertices.push_back(vs[i + 1]); } /* * stack に残っている辺を確定する。 */ for ( int i = 0; i + 1 < (int)stack.size(); ++i ) { edges.emplace_back( stack[i], stack[i + 1] ); } const int original_root = stack[0]; /* * compressed_id を元の頂点番号の昇順に振る。 * * これにより * * compressed_id(v) * * を lower_bound だけで求められる。 */ std::sort( aux_vertices.begin(), aux_vertices.end() ); aux_vertices.erase( std::unique( aux_vertices.begin(), aux_vertices.end() ), aux_vertices.end() ); res.vertex = std::move(aux_vertices); const int m = res.size(); res.graph.assign(m, {}); res.parent.assign(m, -1); res.parent_edge_length.assign(m, 0); res.is_terminal.assign(m, false); /* * Auxiliary Tree の頂点であることが分かっている場合の * original -> compressed。 * * compressed_id() と異なり存在チェックを省いている。 */ auto id = [&](int v) -> int { auto it = std::lower_bound( res.vertex.begin(), res.vertex.end(), v ); assert( it != res.vertex.end() && *it == v ); return (int)(it - res.vertex.begin()); }; res.root = id(original_root); /* * 元々クエリで指定された頂点。 */ for (int v : vs) { res.is_terminal[id(v)] = true; } /* * 辺を圧縮後の番号へ変換。 */ for (auto [p, c] : edges) { const int a = id(p); const int b = id(c); /* * p は c の祖先なので、 * 元の木上の距離は depth の差で求まる。 */ const long long length = depth_[c] - depth_[p]; assert(length > 0); res.graph[a].push_back({ b, length }); res.graph[b].push_back({ a, length }); res.parent[b] = a; res.parent_edge_length[b] = length; } return res; } int n_; int root_; // 元の木における深さ std::vector depth_; // Euler Tour での最初の出現位置 // // preorder の順序としても利用する。 std::vector first_; // 元の木における親 std::vector parent_; // Euler Tour 上の RMQ dst_type rmq_; }; int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout<>n; vvi graph(n); for(int i=1;i>u>>v; u--;v--; graph[u].push_back(v); graph[v].push_back(u); } tree_lca lca(graph); int q; cin>>q; while(q--){ int a,b; cin>>a>>b; a--;b--; int c=lca.lca(a,b); if(c==a){ cout<<"Alice"<