結果

問題 No.1094 木登り / Climbing tree
ユーザー ntuda
提出日時 2024-07-20 19:49:29
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,482 bytes
コンパイル時間 271 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 148,736 KB
最終ジャッジ日時 2024-07-20 19:49:37
合計ジャッジ時間 7,826 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other TLE * 1 -- * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

from math import log2
N = int(input())
E = [[] for _ in range(N)]
for _ in range(N - 1):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    E[a].append((b,c))
    E[b].append((a,c))

NL = int(log2(N)) + 2
P = [[0] * N for _ in range(NL)]
D = [-1] * N
C = [0] * N

def dfs(x, d):
    for y,c in E[x]:
        if D[y] == -1:
            C[y] = C[x] + c
            P[0][y] = x
            D[y] = d + 1
            dfs(y, d + 1)

D[0] = 0
dfs(0, 0)

# ダブリングの計算
for i in range(NL - 1):
    for j in range(N):
        P[i + 1][j] = P[i][P[i][j]]

for _ in range(int(input())):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    # 同じ深さの頂点まで深い方を遡らせる
    da = D[a]
    db = D[b]
    if da < db:
        da, db = db, da
        a, b = b, a
    aa = a
    if da > db:
        dd = da - db
        i = 0
        while dd > 0:
            if dd & 1:
                aa = P[i][aa]
            i += 1
            dd >>= 1

    # 二分探索でLCAを求める
    lb = -1
    ub = max(D)
    mida = aa
    midb = b
    while ub - lb > 1:
        mid = (ub + lb) // 2
        i = 0
        while mid > 0:
            if mid & 1:
                mida = P[i][mida]
                midb = P[i][midb]
            i += 1
            mid >>= 1
        if mida == midb:
            ub = mid
        else:
            lb = mid
    # LCAからの2頂点の距離の和が答え
    ans = C[a] + C[b] - 2 * C[mida]
    print(ans)
0