結果

問題 No.3825 Jump
コンテスト
ユーザー Rho
提出日時 2026-11-14 19:46:01
言語 PyPy3
(8.0.1 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 1,265 ms / 2,000 ms
+ 352µs
コード長 2,274 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 81 ms
コンパイル使用メモリ 64,604 KB
実行使用メモリ 367,152 KB
最終ジャッジ日時 2026-11-22 13:04:29
合計ジャッジ時間 22,427 ms
ジャッジサーバーID
(参考情報)
judge4_0 / judge5_0
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code

import sys

# このコードは、zeta7532 が人力で書いた C++ コードを
# できるだけそのまま Python に言語変換したものです。

sys.setrecursionlimit(1 << 25)
input = sys.stdin.buffer.readline

MOD = 998244353


class LCA:
    def __init__(self, G, root=0):
        self.init(G, root)

    def init(self, G, root=0):
        v = len(G)
        k = 1
        while (1 << k) < v:
            k += 1

        self.par = [[-1] * v for _ in range(k)]
        self.dis = [-1] * v

        self.dfs(G, root, -1, 0)

        for i in range(k - 1):
            for j in range(v):
                if self.par[i][j] < 0:
                    self.par[i + 1][j] = -1
                else:
                    self.par[i + 1][j] = self.par[i][self.par[i][j]]

    def dfs(self, G, v, p, d):
        self.par[0][v] = p
        self.dis[v] = d

        for nv in G[v]:
            if nv != p:
                self.dfs(G, nv, v, d + 1)

    def query(self, u, v):
        if self.dis[u] < self.dis[v]:
            u, v = v, u

        K = len(self.par)

        for k in range(K):
            if ((self.dis[u] - self.dis[v]) >> k) & 1:
                u = self.par[k][u]

        if u == v:
            return u

        for k in range(K - 1, -1, -1):
            if self.par[k][u] != self.par[k][v]:
                u = self.par[k][u]
                v = self.par[k][v]

        return self.par[0][u]

    def get_dis(self, u, v):
        return self.dis[u] + self.dis[v] - 2 * self.dis[self.query(u, v)]


def f(x, y):
    if x <= y:
        return 1
    return 1 - f(y, (x - y + 1) // 2)


def main():
    N = int(input())
    G = [[] for _ in range(N)]

    for _ in range(N - 1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        G[u].append(v)
        G[v].append(u)

    lca = LCA(G)

    Q = int(input())
    output = []

    for _ in range(Q):
        a, b = map(int, input().split())
        a -= 1
        b -= 1

        q = lca.query(a, b)
        dis_a = lca.dis[a] - lca.dis[q]
        dis_b = lca.dis[b] - lca.dis[q]

        ans = f(dis_a, dis_b)

        if ans:
            output.append("Alice")
        else:
            output.append("Bob")

    print("\n".join(output))


if __name__ == "__main__":
    main()
0