結果

問題 No.1094 木登り / Climbing tree
ユーザー ntudantuda
提出日時 2024-07-21 21:11:32
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,518 bytes
コンパイル時間 242 ms
コンパイル使用メモリ 82,540 KB
実行使用メモリ 324,600 KB
最終ジャッジ日時 2024-07-21 21:12:13
合計ジャッジ時間 39,453 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 39 ms
54,196 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
権限があれば一括ダウンロードができます

ソースコード

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)]
P[0] = list(range(N))
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[1][y] = x
            D[y] = d + 1
            dfs(y, d + 1)

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

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

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 = 1
    while dd > 0:
        if dd & 1:
            aa = P[i][aa]
        i += 1
        dd >>= 1
    # 二分探索でLCAを求める
    lb = -1
    ub = db + 1
    mida = aa
    midb = b
    while ub - lb > 1:
        mid = (ub + lb) // 2
        i = 1
        tmp = mid
        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
    # LCAからの2頂点の距離の和が答え

    ans = C[a] + C[b] - 2 * C[mida]
    print(ans)
0