結果
問題 | No.1094 木登り / Climbing tree |
ユーザー |
![]() |
提出日時 | 2020-06-28 16:24:53 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,516 bytes |
コンパイル時間 | 301 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 93,724 KB |
最終ジャッジ日時 | 2024-09-14 22:25:32 |
合計ジャッジ時間 | 5,185 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | TLE * 1 -- * 25 |
ソースコード
from collections import dequeN = int(input())E = [[] for _ in range(N)]for _ in range(N-1):a,b,c = map(int, input().split())E[a-1].append(c*N+b-1)E[b-1].append(c*N+a-1)par = [-1]*Nrnk = [-1]*Npar[0] = 0rnk[0] = 0q = deque()q.append((0, 0))while q:temp = q.popleft()v = temp[0]r = temp[1]for j in E[v]:j %= Nif par[j] < 0:par[j] = vrnk[j] = r+1q.append((j, r+1))#2^k上の祖先を求めるpar[0] = 0LV = (N-1).bit_length()kpar = [par]for k in range(LV):T = [0]*Nfor i in range(N):if par[i] == 0:continueT[i] = par[par[i]]kpar.append(T)par = T#LCAをO(logN)で求めるdef lca(u, v):if rnk[u] > rnk[v]:u, v = v, ud = rnk[v]-rnk[u]for i in range(LV+1):if d & 1:v = kpar[i][v]d >>= 1if u == v:return ufor k in range(LV-1, -1, -1):pu = kpar[k][u]pv = kpar[k][v]if pu != pv:u = puv = pvreturn kpar[0][u]dist = [-1]*Ndist[0] = 0q = deque()q.append((0, 0))while q:temp = q.popleft()u = temp[0]r = temp[1]for e in E[u]:v = e%Nrt = e//Nif dist[v] >= 0:continueq.append((v, r+rt))dist[v] = r+rtQ = int(input())for _ in range(Q):s,t = map(int, input().split())s -= 1t -= 1an = lca(s, t)print(dist[s]+dist[t]-2*dist[an])