ダブリングで祖先を飛ぶ
1回の移動先を保存し、その2回先、4回先、8回先を前計算。移動回数の2進数に沿ってジャンプします。
言語：Python / 計算量：前処理 O(N log K)、質問 O(log K)
前提：DFSと木の親子関係
考え方
- up[k][v] は v の 2^k 回先。
- up[k+1][v]=up[k][up[k][v]]。
- 木のLCAでは深さを揃えてから、祖先が異なる最大のジャンプで近づけます。
具体例
親が [0,0,1,2] の鎖。頂点3の2回先は1、3回先は0です。
実装
parent=[0,0,1,2];LOG=4
up=[parent]
for k in range(1,LOG):
up.append([up[k-1][up[k-1][v]] for v in range(4)])
v=3;steps=3
for k in range(LOG):
if steps>>k&1:v=up[k][v]
print(v)注意する条件
LOG は N だけでなく最大移動回数にも依存します。根の親を根自身にすると境界を揃えられます。
確認問題
parent=[0,0,1,2] で頂点3の2回先は？
解答と理由
1
3→2→1です。
実装課題
N K、各頂点の次の頂点 A（0始まり）。頂点0からK回移動した頂点。N≤200000、0≤K≤10^18。
入力:
3 4
1 2 0
出力:
1参考実装
n,k=map(int,input().split());a=list(map(int,input().split()))
v=0
while k:
if k&1:v=a[v]
a=[a[a[i]] for i in range(n)]
k>>=1
print(v)