結果

問題 No.1094 木登り / Climbing tree
ユーザー ntuda
提出日時 2024-07-21 23:24:12
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,862 ms / 2,000 ms
コード長 1,742 bytes
コンパイル時間 141 ms
コンパイル使用メモリ 82,576 KB
実行使用メモリ 319,808 KB
最終ジャッジ日時 2024-07-21 23:24:57
合計ジャッジ時間 40,900 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(200050)

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]]

#print("a","aa","b","ub","mida","|","D[a]","D[aa]","D[b]","D[mida]","|","ans")
for q 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
    dd = da - db
    i = 0
    while dd > 0:
        if dd & 1:
            aa = P[i][aa]
        i += 1
        dd >>= 1

    # 二分探索でLCAを求める
    lb = -1
    ub = db + 10
    while ub - lb > 1:
        mid = (ub + lb) // 2
        i = 0
        tmp = mid
        mida = aa
        midb = b
        while tmp > 0:
            if tmp & 1:
                mida = P[i][mida]
                midb = P[i][midb]
            i += 1
            tmp >>= 1
        if mida == midb:
            ub = mid
        else:
            lb = mid
    mida = aa
    i = 0
    while ub > 0:
        if ub & 1:
            mida = P[i][mida]
        i += 1
        ub >>= 1
    ans = C[a] + C[b] - 2 * C[mida]
    #print(a+1,b+1,ans)
    #print(a,aa,b,ub,mida,"|",D[a],D[aa],D[b],D[mida],"|",ans)
    print(ans)
0