結果
問題 | No.1094 木登り / Climbing tree |
ユーザー | lloyz |
提出日時 | 2022-10-14 00:13:44 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,711 ms / 2,000 ms |
コード長 | 3,539 bytes |
コンパイル時間 | 1,718 ms |
コンパイル使用メモリ | 85,992 KB |
実行使用メモリ | 162,176 KB |
最終ジャッジ日時 | 2023-09-08 19:19:25 |
合計ジャッジ時間 | 41,146 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 91 ms
71,364 KB |
testcase_01 | AC | 1,699 ms
142,984 KB |
testcase_02 | AC | 436 ms
162,176 KB |
testcase_03 | AC | 500 ms
83,484 KB |
testcase_04 | AC | 650 ms
108,260 KB |
testcase_05 | AC | 1,048 ms
136,292 KB |
testcase_06 | AC | 877 ms
99,436 KB |
testcase_07 | AC | 1,675 ms
144,284 KB |
testcase_08 | AC | 1,659 ms
144,864 KB |
testcase_09 | AC | 1,702 ms
144,388 KB |
testcase_10 | AC | 1,623 ms
144,040 KB |
testcase_11 | AC | 1,641 ms
142,944 KB |
testcase_12 | AC | 1,635 ms
144,044 KB |
testcase_13 | AC | 1,658 ms
143,208 KB |
testcase_14 | AC | 1,694 ms
143,452 KB |
testcase_15 | AC | 691 ms
95,180 KB |
testcase_16 | AC | 851 ms
142,212 KB |
testcase_17 | AC | 756 ms
114,496 KB |
testcase_18 | AC | 726 ms
105,132 KB |
testcase_19 | AC | 832 ms
131,032 KB |
testcase_20 | AC | 1,711 ms
144,200 KB |
testcase_21 | AC | 779 ms
118,140 KB |
testcase_22 | AC | 1,625 ms
144,616 KB |
testcase_23 | AC | 1,670 ms
144,420 KB |
testcase_24 | AC | 1,604 ms
143,548 KB |
testcase_25 | AC | 1,614 ms
142,672 KB |
testcase_26 | AC | 1,640 ms
143,400 KB |
ソースコード
class HeavyLightDecomposition: # HL 分解 (HLD) def __init__(self, E, root=1): # E は双方向に辺を張った木で、破壊的に有向グラフに変更される # O(N) self.E = E self.root = root self.N = N = len(E) # 頂点数 self.Parent = [-1] * N # 頂点番号 v -> 親ノード self.Size = [-1] * N # 頂点番号 v -> 部分木のサイズ self.dfs1() self.Mapping = [-1] * N # 頂点番号 v -> 内部インデックス self.Head = list(range(N)) # 頂点番号 v -> v を含む heavy path の左端の頂点番号 self.Depth = [0] * N # 頂点番号 v -> 深さ(root から v までの距離) self.dfs2() def dfs1(self): E = self.E Parent, Size = self.Parent, self.Size Path = [self.root] Idx_edge = [0] while Path: v = Path[-1] idx_edge = Idx_edge[-1] Ev = E[v] if idx_edge != len(Ev): # 行きがけ・通りがけ 辺の数だけ実行される u = Ev[idx_edge] Idx_edge[-1] += 1 E[u].remove(v) # 有向グラフならここをコメントアウトする Parent[u] = v Path.append(u) Idx_edge.append(0) else: # 帰りがけ 頂点の数だけ実行される if len(Ev) >= 2: ma = -1 argmax = None for i, u in enumerate(Ev): if Size[u] > ma: ma = Size[u] argmax = i Ev[0], Ev[argmax] = Ev[argmax], Ev[0] Size[v] = sum(Size[u] for u in Ev) + 1 Path.pop() Idx_edge.pop() def dfs2(self): E = self.E Mapping = self.Mapping Head = self.Head Depth = self.Depth k = 0 St = [self.root] while St: v = St.pop() Mapping[v] = k k += 1 Ev = E[v] if Ev: Head[Ev[0]] = Head[v] St += Ev[::-1] for u in Ev: Depth[u] = Depth[v] + 1 # distance を使わないのならここをコメントアウトする def lca(self, v, u): # O(logN) Parent = self.Parent Mapping = self.Mapping Head = self.Head while True: if Mapping[v] > Mapping[u]: v, u = u, v # v の方を根に近くする if Head[v] == Head[u]: return v u = Parent[Head[u]] def distance(self, v, u): # O(logN) Depth = self.Depth return Depth[v] + Depth[u] - 2 * Depth[self.lca(v, u)] from collections import deque n = int(input()) E = [[] for _ in range(n + 1)] EC = [[] for _ in range(n + 1)] for _ in range(n - 1): a, b, c = map(int, input().split()) E[a].append(b) EC[a].append((b, c)) E[b].append(a) EC[b].append((a, c)) INF = 10**18 C = [INF for _ in range(n + 1)] C[1] = 0 Que = deque([1]) while Que: cp = Que.popleft() cc = C[cp] for np, dc in EC[cp]: if cc + dc >= C[np]: continue C[np] = cc + dc Que.append(np) HL = HeavyLightDecomposition(E) q = int(input()) for _ in range(q): s, t = map(int, input().split()) st_lca = HL.lca(s, t) print(C[s] + C[t] - 2 * C[st_lca])