Submit Info #3005

Problem Lang User Status Time Memory
Lowest Common Ancestor pypy3 knuu AC 2001 ms 235.70 MiB

ケース詳細
Name Status Time Memory
example_00 AC 118 ms 32.38 MiB
line_00 AC 1144 ms 180.10 MiB
line_01 AC 1235 ms 235.70 MiB
line_02 AC 727 ms 101.18 MiB
line_03 AC 580 ms 188.04 MiB
line_04 AC 521 ms 137.45 MiB
random_00 AC 1809 ms 162.34 MiB
random_01 AC 2001 ms 175.09 MiB
random_02 AC 870 ms 96.35 MiB
random_03 AC 1152 ms 143.99 MiB
random_04 AC 835 ms 121.68 MiB

from collections import deque class Edge: def __init__(self, dst, weight): self.dst, self.weight = dst, weight def __lt__(self, e): return self.weight > e.weight class Graph: def __init__(self, V): self.V = V self.E = [[] for _ in range(V)] def add_edge(self, src, dst, weight): self.E[src].append(Edge(dst, weight)) class HeavyLightDecomposition: def __init__(self, g, root=0): self.g = g self.vid, self.head = [-1] * g.V, [0] * g.V self.heavy, self.parent = [-1] * g.V, [0] * g.V self.dfs(root) self.bfs(root) def dfs(self, root=-1): stack = [(root, -1, False)] sub, max_sub = [1] * self.g.V, [(0, -1)] * self.g.V while stack: v, par, flag = stack.pop() if not flag: self.parent[v] = par stack.append((v, par, True)) stack.extend((e.dst, v, False) for e in self.g.E[v] if e.dst != par) else: if par != -1: sub[par] += sub[v] max_sub[par] = max(max_sub[par], (sub[v], v)) self.heavy[v] = max_sub[v][1] def bfs(self, root=0): k, que = 0, deque([root]) while que: r = v = que.popleft() while v != -1: self.vid[v], self.head[v] = k, r k += 1 for e in self.g.E[v]: if e.dst != self.parent[v] and e.dst != self.heavy[v]: que.append(e.dst) v = self.heavy[v] def lca(self, u, v): while self.head[u] != self.head[v]: if self.vid[u] > self.vid[v]: u, v = v, u v = self.parent[self.head[v]] else: if self.vid[u] > self.vid[v]: u, v = v, u return u def yosupo(): # https://judge.yosupo.jp/problem/lca N, Q = map(int, input().split()) graph = Graph(N) for i, p in enumerate(map(int, input().split())): graph.add_edge(p, i+1, 1) hld = HeavyLightDecomposition(graph) ans = [hld.lca(*map(int, input().split())) for _ in range(Q)] print(*ans, sep="\n") if __name__ == "__main__": yosupo()