結果

問題 No.3825 Jump
コンテスト
ユーザー zeta7532
提出日時 2026-11-14 19:30:12
言語 Python3
(3.15.2 + numpy 2.5.4 + scipy 1.18.1 + ACL)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
TLE  
実行時間 -
コード長 2,274 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 53 ms
コンパイル使用メモリ 14,848 KB
実行使用メモリ 115,456 KB
最終ジャッジ日時 2026-11-22 12:42:26
合計ジャッジ時間 47,704 ms
ジャッジサーバーID
(参考情報)
judge6_0 / judge5_0
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 25 TLE * 3
権限があれば一括ダウンロードができます

ソースコード

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