結果

問題 No.1094 木登り / Climbing tree
ユーザー takeya_okinotakeya_okino
提出日時 2021-10-23 16:47:18
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,193 bytes
コンパイル時間 179 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 397,344 KB
最終ジャッジ日時 2024-09-25 07:56:38
合計ジャッジ時間 35,640 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

import sys
sys.setrecursionlimit(10**9)
 
n = int(input())
 
e = [[] for i in range(n)]
 
for i in range(n - 1):
  a, b, c = map(int, input().split())
  e[a - 1].append([b - 1, c])
  e[b - 1].append([a - 1, c])
 
depth = [0 for i in range(n)]
 
dp = [[-1 for j in range(40)] for i in range(n)]
 
def dfs(v, p):
  for i in range(len(e[v])):
    if e[v][i][0] != p:
      depth[e[v][i][0]] = depth[v] + e[v][i][1]
      dp[e[v][i][0]][0] = v
      dfs(e[v][i][0], v)
 
dfs(0, -1)

for k in range(1, 40):
  for i in range(n):
    if dp[i][k - 1] >= 0:
      dp[i][k] = dp[dp[i][k - 1]][k - 1]
    else:
      dp[i][k] = -1
 
q = int(input())
 
for i in range(q):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  u = a
  v = b
  if depth[u] < depth[v]:
    t = depth[v] - depth[u]
    for j in range(40):
      if (t & (1 << j)) != 0:
        v = dp[v][j]
  if depth[v] < depth[u]:
    t = depth[u] - depth[v]
    for j in range(40):
      if (t & (1 << j)) != 0:
        u = dp[u][j]
  lca = 0
  for j in reversed(range(40)):
    if dp[u][j] != dp[v][j]:
      u = dp[u][j]
      v = dp[v][j]
  lca = u
  if u != v:
    lca = dp[u][0]    
  print(depth[a] + depth[b] - (2 * depth[lca]))
0