Level Ancestor Problem
LCA、
$ N頂点の根付き木において、頂点$ vの祖先であって深さが$ dの頂点を求める$ Q個のクエリに答える。
オフラインならクエリ先読みで$ O(N+Q)
リファレンス
Offline Level Ancestor Θ(N+Q) / noshi91
Level Ancestor Problem / 37zigen
Level Ancestor Problem Simplified / hdbn
そらで書ける <Θ(N), Θ(log N)> Level Ancestor / suisen
code: LA.python
from collections import deque
def Level_Ancestor(s):
"""
sを根としたLAクエリに答える
G := 木の隣接頂点リスト
Queries := 頂点vに関するクエリ(d, i)が入った三次元リスト (iはクエリ番号)
ans := クエリの結果を保持するリスト
"""
Stack = deque(s)
P = []
used = 0 * N
while Stack:
x = Stack.pop()
if x < 0:
P.pop()
continue
if usedx: continue
usedx = 1
Stack.append(~x)
P.append(x)
for d, i in Queriesx:
if len(P) <= d: continue
ansi = Pd
for y in Gx:
if usedy: continue
Stack.append(y)
N = int(input())
G = [[] for _ in range(N)]
for _ in range(N-1):
a, b = map(int, input().split())
a, b = a-1, b-1
Ga.append(b)
Gb.append(a)
Q = int(input())
Queries = [[] for _ in range(N)]
for i in range(Q):
x, d = map(int, input().split())
Queriesx-1.append(d, i)
ans = -1 * Q
Level_Ancestor(0)
print(*ans)