結果

問題 No.1094 木登り / Climbing tree
ユーザー takeya_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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 1 WA * 6 TLE * 19
権限があれば一括ダウンロードができます

ソースコード

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