結果
問題 | No.1094 木登り / Climbing tree |
ユーザー |
![]() |
提出日時 | 2020-06-28 16:25:18 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,728 ms / 2,000 ms |
コード長 | 1,516 bytes |
コンパイル時間 | 235 ms |
コンパイル使用メモリ | 82,688 KB |
実行使用メモリ | 137,728 KB |
最終ジャッジ日時 | 2024-09-14 22:26:12 |
合計ジャッジ時間 | 37,229 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 26 |
ソースコード
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])