Submit Info #3004

Problem Lang User Status Time Memory
Lowest Common Ancestor python3 knuu AC 4718 ms 237.57 MiB

ケース詳細
Name Status Time Memory
example_00 AC 20 ms 4.01 MiB
line_00 AC 1967 ms 200.68 MiB
line_01 AC 2218 ms 237.57 MiB
line_02 AC 869 ms 49.52 MiB
line_03 AC 1244 ms 220.58 MiB
line_04 AC 991 ms 143.77 MiB
random_00 AC 4157 ms 174.36 MiB
random_01 AC 4718 ms 200.34 MiB
random_02 AC 1557 ms 36.84 MiB
random_03 AC 2497 ms 180.77 MiB
random_04 AC 1950 ms 119.22 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()