結果
問題 | No.1094 木登り / Climbing tree |
ユーザー |
👑 ![]() |
提出日時 | 2020-07-03 03:09:14 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,110 bytes |
コンパイル時間 | 208 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 160,928 KB |
最終ジャッジ日時 | 2024-09-15 23:27:12 |
合計ジャッジ時間 | 30,006 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 11 TLE * 15 |
ソースコード
from collections import dequeJ=19N=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(w*N+v-1)E[v].append(w*N+u-1)T=[None]*(N+1)A=[[1]*J for _ in range(N+1)]Depth=[None]*(N+1)Q=deque()T[1]=0Depth[1]=0Q.append(1)while Q:v=Q.popleft()for x in E[v]:u=x%N+1w=x//Nif T[u]==None:T[u]=T[v]+wDepth[u]=Depth[v]+1A[u][0]=vQ.append(u)for p in range(J-1):for u in range(1,N+1):v=A[u][p]A[u][p+1]=A[v][p]def upper(u,k):i=0while k>0:if k%2==1:u=A[u][i]i+=1k//=2return udef lca(u,v):x=Depth[u]y=Depth[v]u=upper(u,max(x-y,0))v=upper(v,max(y-x,0))if u==v:return ufor j in range(J-1,-1,-1):if A[u][j]!=A[v][j]:u=A[u][j]v=A[v][j]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)])