結果

問題 No.3825 Jump
コンテスト
ユーザー askr58
提出日時 2026-11-22 13:49:15
言語 C++23
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -fplugin=/usr/lib/yukicoder/noavx512-gcc15.so -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 597 ms / 2,000 ms
+ 841µs
コード長 18,919 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,981 ms
コンパイル使用メモリ 363,824 KB
実行使用メモリ 157,076 KB
最終ジャッジ日時 2026-11-22 13:49:38
合計ジャッジ時間 22,573 ms
ジャッジサーバーID
(参考情報)
judge5_0 / judge6_0
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code

// 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 <https://creativecommons.org/publicdomain/zero/1.0/> for details.
//
// [日本語]
// 法律上可能な範囲で、著作者はこのソフトウェアに関する著作権および
// 著作隣接権を含むすべての関連する権利を、全世界でパブリックドメインに
// 提供しています。本ソフトウェアは一切の保証なく配布されます。
// 自由にコピー・改変・再配布・商用利用できます(クレジット表記は不要です)。
// 詳細は <https://creativecommons.org/publicdomain/zero/1.0/deed.ja> を参照してください。
// ※ 英語の文面および CC0 1.0 の正式な条文(英語)が優先されます。

#include <iostream>
#include <bitset>
#include <random>
#include <chrono>
#include <iomanip>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <string>
#include <stack>
#include <ranges>
#include <algorithm>
#include <vector>
using namespace std;
using ll=long long;

#include <atcoder/all>
using mint=atcoder::modint998244353;

ostream& operator<<(ostream& os,const mint& x){
	os<<x.val();
	return os;
}
istream& operator>>(istream& is,mint& x){
	int t;
	is>>t;
	x=t;
	return is;
}

template <typename S,typename T>
ostream& operator<<(ostream& os,const pair<S,T>& p);
template <typename S,typename T>
istream& operator>>(istream& is,pair<S,T>& p);
template <typename T,size_t n>
ostream& operator<<(ostream& os,const array<T,n>& arr);
template <typename T,size_t n>
istream& operator>>(istream& is,array<T,n>& arr);
template <typename T>
ostream& operator<<(ostream& os,const vector<T>& vec);
template <typename T>
istream& operator>>(istream& is,vector<T>& vec);

template <typename S,typename T>
ostream& operator<<(ostream& os,const pair<S,T>& p){
	os<<p.first<<" "<<p.second;
	return os;
}
template <typename S,typename T>
istream& operator>>(istream& is,pair<S,T>& p){
	is>>p.first>>p.second;
	return is;
}

template <typename T,size_t n>
ostream& operator<<(ostream& os,const array<T,n>& arr){
	for(int i=0;i<n;i++)os<<arr[i]<<(i+1==n?"":" ");
	return os;
}
template <typename T,size_t n>
istream& operator>>(istream& is,array<T,n>& arr){
	for(int i=0;i<n;i++)is>>arr[i];
	return is;
}
template <typename T>
ostream& operator<<(ostream& os,const vector<T>& vec){
	for(int i=0;i<(int)vec.size();i++)os<<vec[i]<<(i+1==(int)vec.size()?"":" ");
	return os;
}
template <typename T>
istream& operator>>(istream& is,vector<T>& vec){
	for(int i=0;i<(int)vec.size();i++)is>>vec[i];
	return is;
}

template<class... Vecs>
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 <class... Vecs>
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 <typename C>
C make_unique(C vec){
	ranges::sort(vec);
	vec.erase(unique(vec.begin(),vec.end()),vec.end());
	return vec;
}

vector<int> Iota(int n,int s=0){
	vector<int> res(n);
	iota(res.begin(),res.end(),s);
	return res;
}

vector<ll> Iotall(int n,ll s=0){
	vector<ll> res(n);
	iota(res.begin(),res.end(),s);
	return res;
}
void YESNO(bool f){
	if(f)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}

using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using vvvl=vector<vector<vector<ll>>>; 
using vi=vector<int>;
using vvi=vector<vector<int>>;
using vvvi=vector<vector<vector<int>>>;
using vmi=vector<mint>;
using vvmi=vector<vector<mint>>;
using vvvmi=vector<vector<vector<mint>>>;

//https://atcoder.jp/contests/awc0150/submissions/79608947
// generated by ChatGPT outside of contest time.
#include <algorithm>
#include <cassert>
#include <vector>

template <class S, S (*op)(S, S), S (*e)()>
struct disjoint_sparse_table {
  public:
    disjoint_sparse_table() : disjoint_sparse_table(0) {}

    explicit disjoint_sparse_table(int n)
        : disjoint_sparse_table(std::vector<S>(n, e())) {}

    explicit disjoint_sparse_table(const std::vector<S>& v)
        : _n((int)v.size()), data_(v) {
        log_ = 0;
        while ((1LL << log_) < _n) ++log_;

        table_.assign(log_, std::vector<S>(_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<long long>(l + half, _n);
                const int r =
                    (int)std::min<long long>(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<unsigned>(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 <bool (*f)(S)>
    int max_right(int l) const {
        return max_right(l, f);
    }

    template <class F>
    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 <bool (*f)(S)>
    int min_left(int r) const {
        return min_left(r, f);
    }

    template <class F>
    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<S> data_;
    std::vector<std::vector<S>> table_;
};

//https://atcoder.jp/contests/awc0150/submissions/79608947
// generated by ChatGPT outside of contest time.
#include <algorithm>
#include <cassert>
#include <limits>
#include <utility>
#include <vector>

namespace tree_lca_detail {

using rmq_value = std::pair<long long, int>;
// {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<long long>::max(),
        std::numeric_limits<int>::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<std::vector<edge>> graph;

		// compressed vertex -> original vertex
		//
		// 元の頂点番号の昇順になっている。
		std::vector<int> vertex;

		// root を根としたときの親
		std::vector<int> parent;

		// parent との辺の長さ
		std::vector<long long> parent_edge_length;

		// 元々 make_auxiliary_tree() に渡された頂点なら true
		std::vector<char> 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<std::vector<int>>& 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<rmq_value> tour;
        tour.reserve(2 * n_ - 1);

        struct frame {
            int v;
            int p;
            int next;
        };

        std::vector<frame> 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 <typename T>
    explicit tree_lca(
        const std::vector<std::vector<std::pair<T,int>>>& 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<rmq_value> tour;
        tour.reserve(2 * n_ - 1);

        struct frame {
            int v;
            int p;
            int next;
        };

        std::vector<frame> 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<int> 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<int> stack;
		stack.reserve(2 * k);

		/*
		 * Auxiliary Tree に出現した頂点。
		 *
		 * この時点ではソートされていない。
		 */
		std::vector<int> aux_vertices;
		aux_vertices.reserve(2 * k);

		/*
		 * Auxiliary Tree の有向辺
		 *
		 * {parent, child}
		 *
		 * いずれも元の木における頂点番号。
		 */
		std::vector<std::pair<int, int>> 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<long long> depth_;

    // Euler Tour での最初の出現位置
    //
    // preorder の順序としても利用する。
    std::vector<int> first_;

    // 元の木における親
    std::vector<int> parent_;

    // Euler Tour 上の RMQ
    dst_type rmq_;
};
int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);
	int n;
	cin>>n;
	vvi graph(n);
	for(int i=1;i<n;i++){
		int u,v;
		cin>>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"<<endl;
			continue;
		}
		if(c==b){
			cout<<"Bob"<<endl;
			continue;
		}
		int d1=lca.dist(a,c),d2=lca.dist(b,c);
		while(1){
			if(d1<=d2){
				cout<<"Alice"<<endl;
				break;
			}else{
				int d=d1+d2;
				d1-=d/2;
			}
			if(d2<=d1){
				cout<<"Bob"<<endl;
				break;
			}else{
				d2-=(d1+d2)/2;
			}
		}
	}
}
				

0