結果

問題 No.1094 木登り / Climbing tree
ユーザー ntudantuda
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 36 ms
53,592 KB
testcase_01 AC 1,543 ms
144,048 KB
testcase_02 AC 646 ms
319,808 KB
testcase_03 AC 439 ms
80,820 KB
testcase_04 AC 513 ms
107,088 KB
testcase_05 AC 665 ms
135,020 KB
testcase_06 AC 867 ms
98,580 KB
testcase_07 AC 1,604 ms
144,156 KB
testcase_08 AC 1,573 ms
143,864 KB
testcase_09 AC 1,572 ms
143,840 KB
testcase_10 AC 1,604 ms
143,980 KB
testcase_11 AC 1,537 ms
144,064 KB
testcase_12 AC 1,537 ms
143,968 KB
testcase_13 AC 1,549 ms
143,964 KB
testcase_14 AC 1,544 ms
143,056 KB
testcase_15 AC 1,084 ms
130,944 KB
testcase_16 AC 1,862 ms
267,700 KB
testcase_17 AC 1,388 ms
182,000 KB
testcase_18 AC 1,246 ms
156,932 KB
testcase_19 AC 1,661 ms
226,372 KB
testcase_20 AC 1,573 ms
143,416 KB
testcase_21 AC 1,476 ms
198,300 KB
testcase_22 AC 1,531 ms
144,296 KB
testcase_23 AC 1,498 ms
143,760 KB
testcase_24 AC 1,588 ms
143,960 KB
testcase_25 AC 1,568 ms
144,180 KB
testcase_26 AC 1,607 ms
144,744 KB
権限があれば一括ダウンロードができます

ソースコード

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