DoublingによるLCA
Abstract
最小共通祖先 (Lowest Common Ancestor) はDoublingを利用することで計算できる. Explanation
TODO 書く.
Implementation
グラフ構築
Input
グラフの頂点数 N
グラフの各辺の始点 init, 終点 end, 重み weight
Output
グラフの隣接リスト E
Time complexity
$ O(|E|)time.
LCA計算の前処理
Input
なし
Output
各頂点の親を記録したリスト parent
各頂点の根からの距離 dist
各頂点の根からの深さ depth
Doubling用配列 next
Time complexity
$ O(|V| \log |V|)time.
LCAの計算
Input
グラフの2頂点 u, v
Output
u と v のLCA lca
Time complexity
$ O(\log |V|)time.
2頂点の距離計算
Input
グラフの2頂点 u, v
Output
u と v の距離 d
Time complexity
$ O(\log |V|)time.
code:python
class LCA:
def __init__(self, N):
self.E = [[] for _ in range(N)]
def add_edge(self, init, end, weight, undirected=True):
self.Einit.append((end, weight)) if undirected: self.Eend.append((init, weight)) def lca_initialize(self):
self._dfs(0)
self._doubling()
def _dfs(self, root):
self.parent = parent = None * self.N # parentsv: the parent of the vertex v self.depth = depth = None * self.N # depthv: the depth of the vertex v from the root self.dist = dist = float('inf') * self.N # distv: the distance of the vertex v from the root. E = self.E
while stack:
v = stack.pop()
if depthu is not None: continue parentu = v; depthu = depthv + 1; distu = distv + d stack.append(u)
def _doubling(self):
# O(N log N) time
N, D, parent = self.N, self.D, self.parent
self.next = nxt = [-1 * N for _ in range(D)] for v in range(N): nxt0v = parentv for d in range(D - 1):
for v in range(N):
def lca(self, u, v):
# O(log N) time
depth, nxt = self.depth, self.next
# the depth of v is set to be no less than that of u
if depthu > depthv: u, v = v, u # find the ancestor of v with the same depth as that of u
for i in range(diff.bit_length()):
if diff & (1 << i): v = nxtiv if u == v: return u
for i in range(depthu.bit_length() - 1, -1, -1): if pu != pv: u, v = pu, pv
def distance(self, u, v):
dist = self.dist
w = self.lca(u, v)
return distu + distv - 2 * distw Verification
ABC014 D - 閉路 (PyPy3. input = sys.stdin.readline とするとPython 3でも通る) References