PAST1K

https://gyazo.com/735b48c1d33a9397fd177016e9fd6b8a

考えたこと

巨大な木が与えられてaがbの子孫かを判定する問題

素朴にやるとO(NQ)

バランスした木なら対数オーダーだから問題ないのだが、すごく偏ってる時に問題

計算結果をキャッシュしたいが、素朴にキャッシュすると空間がN^2になるのでダメ

枝分かれのないパスをキャッシュ？

ダメ、二股の分岐がN/2個続くグラフがある

思考の分岐A

偏ってるときだけキャッシュすれば良い？

前処理で一定以上に深い点だけキャッシュ

ダメ、N/2より深い頂点をN/2個作れる

思考の分岐A

キャッシュ済みの経路に後から合流したことの判定を低コストにできれば良い

例えばある頂点から根までをたどる

この時、キャッシュ用の配列Aiにたどった頂点をインクリメントしながら記録

別途キャッシュを見つけるための配列Bにキャッシュ番号iを書き込んでいく

2回目以降、親を辿る際にBを見れば定数オーダーで既にキャッシュされてるかどうかわかる

既にキャッシュされてるならそのキャッシュの目的頂点の番号を見て今の頂点の番号との大小関係を見れば祖先にいるかどうか反対できる

キャッシュに見つからなくて素朴に親をたどっていくプロセスは最大N回しか起こらない

キャッシュにヒットした後は定数オーダー

追記: この方法は細かいキャッシュをたくさん作られるような入力の時に空間計算量が大きくなるからダメ

公式解説

lca(x, y) = x ならyはxの子孫

ダブリングによる最小共通祖先の求めかたの一部で実現できる

まず各頂点の深さを求める、これは線形オーダー

2^k個先の親を求める、k一つにつき線形オーダーで、kの値は対数オーダー

与えられた2頂点のうち、深い方の親をたどって深さを揃える

この後最小共通祖先を求めるためには二分探索が必要だが、今回は浅い方の頂点が最小共通祖先であるかどうかの判定だけで良い

別解

行きがけ順で頂点を並べる

ある頂点の子孫の頂点は、その頂点を始点とする区間に含まれる

行きがけ順での頂点の位置pos(x)と、区間終点の位置end(x)を配列で持っておけば pos(x) < pos(y) <= end(x) ならyはxの子孫

定数オーダー

AC

0オリジンに変える

各頂点から親へのポインタが渡されているところを、親から子へのポインタに付け替える

各頂点の深さをDFSで求める

ダブリングで2^i個上の頂点を求める

各クエリに対して深さの差dを求め、aからdだけ上の頂点がbに一致するか判定する

code:python

def solve(N, PS, Q, QS):

# PAST1K

# to 0-origin

from collections import defaultdict

children = defaultdict(list)

for i, p in enumerate(PS):

# calc depth

def visit(v):

visit(c)

visit(root)

# doubling

for _i in range(20):

for i in range(N):

parents.append(next)

for a, b in QS:

a -= 1

b -= 1

if d < 0:

print("No")

continue

# find d-th parent of a

p = a

for i in range(20):

if d % 2:

d //= 2

if p == b:

print("Yes")

else:

print("No")