Level Ancestor Problem
LCA、
$ N頂点の根付き木において、頂点$ vの祖先であって深さが$ dの頂点を求める$ Q個のクエリに答える。
リファレンス
code: LA.python
from collections import deque
def Level_Ancestor(s):
"""
sを根としたLAクエリに答える
G := 木の隣接頂点リスト
Queries := 頂点vに関するクエリ(d, i)が入った三次元リスト (iはクエリ番号)
ans := クエリの結果を保持するリスト
"""
P = []
while Stack:
x = Stack.pop()
if x < 0:
P.pop()
continue
Stack.append(~x)
P.append(x)
if len(P) <= d: 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
Q = int(input())
Queries = [[] for _ in range(N)]
for i in range(Q):
x, d = map(int, input().split())
Level_Ancestor(0)
print(*ans)