結果
問題 | No.1094 木登り / Climbing tree |
ユーザー |
👑 ![]() |
提出日時 | 2020-06-26 00:42:44 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,106 bytes |
コンパイル時間 | 160 ms |
コンパイル使用メモリ | 82,428 KB |
実行使用メモリ | 201,852 KB |
最終ジャッジ日時 | 2024-09-14 22:19:56 |
合計ジャッジ時間 | 44,547 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 1 WA * 10 TLE * 15 |
ソースコード
from collections import dequeJ=18N=int(input())E={i:[] for i in range(1,N+1)}for _ in range(N-1):u,v,w=map(int,input().split())E[u].append((v,w))E[v].append((u,w))T={i:None for i in range(1,N+1)}A=[[1]*J for _ in range(N+1)]Depth={i:None for i in range(1,N+1)}Q=deque()T[1]=0Depth[1]=0Q.append(1)while Q:v=Q.popleft()for (u,w) in E[v]:if T[u]==None:T[u]=T[v]+wDepth[u]=Depth[v]+1A[u][0]=vQ.append(u)for p in range(1,J):for u in range(1,N+1):v=A[u][p-1]A[u][p]=A[v][p-1]def upper(u,k):i=0while k>0:if k%2==1:u=A[u][i]i+=1k//=2return udef lca(u,v):if u==v:return ux=Depth[u]y=Depth[v]u=upper(u,max(x-y,0))v=upper(v,max(y-x,0))P=2**(J-1)for i in range(J-1,-1,-1):if A[u][i]!=A[v][i]:u=A[u][i]v=A[v][i]return A[u][0]Q=int(input())for _ in range(Q):u,v=map(int,input().split())print(T[u]+T[v]-2*T[lca(u,v)])