結果

問題 No.3825 Jump
コンテスト
ユーザー kwm_t
提出日時 2026-11-22 14:07:45
言語 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  
実行時間 827 ms / 2,000 ms
+ 609µs
コード長 4,997 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,432 ms
コンパイル使用メモリ 354,424 KB
実行使用メモリ 65,716 KB
最終ジャッジ日時 2026-11-22 14:08:10
合計ジャッジ時間 25,550 ms
ジャッジサーバーID
(参考情報)
judge2_0 / judge4_0
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code

#include <bits/stdc++.h>
//#include <atcoder/all>
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<int, int>
template<typename A, typename B> inline bool chmax(A& a, const B& b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> 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 <vector>
#include <algorithm>

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<std::vector<int>> g;

	std::vector<int> depth;
	std::vector<int> in, out;
	std::vector<int> parent[MAXLOGV];

public:
	LcaTree(std::vector<std::vector<int>> 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<int> get_path(int u, int v) const {
		int p = lca(u, v);

		std::vector<int> left;
		std::vector<int> 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<int>());
	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;
}
0