結果
| 問題 | No.3825 Jump |
| コンテスト | |
| ユーザー |
kwm_t
|
| 提出日時 | 2026-11-22 14:07:45 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 827 ms / 2,000 ms |
| + 609µs | |
| コード長 | 4,997 bytes |
| 記録 | |
| コンパイル時間 | 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 |
ソースコード
#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;
}
kwm_t