結果

問題 No.1094 木登り / Climbing tree
ユーザー ntuda
提出日時 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other WA * 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)]
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)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0