結果

問題 No.1094 木登り / Climbing tree
ユーザー koheijkt
提出日時 2026-01-19 12:57:48
言語 PyPy3
(7.3.17)
結果
AC  
実行時間 1,441 ms / 2,000 ms
コード長 2,319 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 347 ms
コンパイル使用メモリ 82,680 KB
実行使用メモリ 151,804 KB
最終ジャッジ日時 2026-01-19 12:58:29
合計ジャッジ時間 34,655 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from collections import deque
N = int(input())
G = [list() for _ in range(N)]
for i in range(N - 1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    G[u].append((v, w))
    G[v].append((u, w))

# BFS で深さ調べる
dist = [-1] * N
dist[0] = 0
que = deque([0])
while que:
    pos = que.popleft()
    for nex, w in G[pos]:
        if dist[nex] == -1:
            dist[nex] = dist[pos] + w
            que.append(nex)

# LCA を求める
#ancestor[2**i個上][頂点jから]
limit = 20 # N = 10**6 程度のときは 最長で 2**20 個くらい上を見る必要がある

par = [-2]*N
par[0] = -1
depth = [-1]*N
depth[0] = 0
ancestor = [[-2]*N for _ in range(limit+1)] # 2**0 ~ 2**limit

# DFS で探索
stack = []
stack.append((0, -1)) # (頂点, 親)
while stack:
    pos, oya = stack.pop()
    # 子どもたち
    for nex, w in G[pos]:
        if nex == oya:
            continue
        par[nex] = pos
        depth[nex] = depth[pos] + 1
        stack.append((nex, pos))

# 根付き木における親が特定できたので ancestor table つくる
# 種まき
for j in range(N):
    ancestor[0][j] = par[j]
# DP
for i in range(1, limit+1):
    for j in range(N):
        x = ancestor[i-1][j]
        if x != -1:
            ancestor[i][j] = ancestor[i-1][ancestor[i-1][j]]
        else:
            ancestor[i][j] = -1

# LCA を求める（関数を作る）
def lca(u:int, v:int): #頂点uとvのLCA
    # u の方が深い とする
    if depth[u] < depth[v]:
        u, v = v, u
    # depth[u] >= depth[v] となった
    diff = depth[u] - depth[v]
    # u を diff歩だけ上に歩かせる
    for i in range(limit + 1):
        if (diff >> i) & 1 == 1:
            u = ancestor[i][u]
    # この時点で u, v は同じ depth となった
    if u == v:
        return u

    curr_depth = depth[u]
    k = (curr_depth - 1).bit_length() # k: curr_depth 以上の最も近い2の累乗2**k

    for i in range(k, -1, -1):
        nextu = ancestor[i][u]
        nextv = ancestor[i][v]
        if nextu != nextv: #上昇が足りない
            u = nextu
            v = nextv
    
    return ancestor[0][u]

Q = int(input())

for i in range(Q):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    l = lca(s, t)
    ans = dist[s] + dist[t] - 2*dist[l]
    print(ans)
0