level ancestor (LA) と呼ばれる有名問題があります。以下のような形式の問題です。

根つき木 \(T\) が与えられる。この木に対し、「頂点 \(v\) の祖先のうち、深さが \(l\) のものを答えよ」というクエリたちを処理せよ。

（頂点 \(v\) の深さは \(l\) 以上であるとし、そのような答えは必ず存在することにしておきます。）

競技プログラミングにおいては「頂点 \(v\) から、祖先を辿る操作を \(k\) 回行ったときの頂点はなにか？」という形式で出題されることが多いですが、これは簡単な言い換えで LA に帰着できます。 計算機科学の文脈では LA の形式で言及されることが多いような気がしています。

（解説のあらすじ）

1. LA が使える形に言い換える
   • これにより、\(K\) に依存しない計算量になる
2. LA が実は高速に解けることを伝える

---

さて、ABC 367 E について考えます。 各 \(i\) (\(1\le i\le N\)) に対して \(i\) から \(X_i\) への有向辺があるような \(N\) 頂点の有向グラフ \(G\) を考えます。

\(G\) のような、各頂点の出次数が \(1\) の有向グラフは functional graph と呼ばれます。 functional graph の弱連結成分（向きを無視したときの連結成分）の各々は、サイクルをちょうど一つずつ持ちます。 各サイクルの頂点を一つずつ「サイクルの代表元」として選んでおきます。

ここで、次のような \(N+1\) 頂点の根つき木 \(T\) を考えます。 根を \(N+1\) とし、各 \(1\le i\le N\) について、下記で親を定めます。

• \(i\) がサイクルの代表元ならば、\(i\) の親は \(N+1\) である。
• そうでないならば、\(i\) の親は \(X_i\) である。

また、サイクルの代表元 \(r\) に対して、下記を満たすような配列 \(\langle c_1, c_2, \dots, c_{n_r}\rangle\) を持っておきます（要するに、\(r\) から始めたサイクルの列です）。

• \(c_1 = X_{c_{n_r}} = r\) かつ \(c_{i+1} = X_{c_i}\) (\(2 \le i< n_r\))

（\(r\) が先頭に来ること自体は本質ではないので、実装方針に応じて調整してよいです。順序通りに並んでいるのが大事です。）

---

さて、元問題における \(A'_i\) を求めましょう。

木 \(T\) における \(i\) の深さを \(d_i\) とします。 \(d_i-1 \ge K\) であれば、\(T\) 上で \(i\) から祖先に \(K\) 回辿った頂点が答えとなります。

そうでないとき、\(d_i-1\) 回辿った頂点はサイクルの代表元です。 残り \(K-(d_i-1)\) 回辿った頂点は、上で作った配列と簡単な四則演算と mod によって求めることができます。

※ 式として簡単というだけで、添字の ±1 や符号などは間違いやすいことが予想されます。落ちついて計算しましょう。0-indexed / 1-indexed などでも混乱しないようにしましょう。

---

あとは LA を求めるパートだけです。 頂点数を \(N\) として、以下の計算量のアルゴリズムが知られています。

• クエリ数 \(Q\) のオフライン（予めクエリの内容をすべて知っている状態で解く問題設定・またそのアルゴリズム）で \(O(N+Q)\) 時間
• オンライン（クエリに答えるまで次のクエリの内容を知らされない問題設定・またそのアルゴリズム）で \(\langle O(N), O(1) \rangle\) 時間
  • \(\langle f(n), g(n)\rangle\) は、前処理 \(f(n)\) 時間、クエリあたり \(g(n)\) 時間の意味の記法

前者は Offline Level Ancestor Θ(N+Q), noshi91のメモ、後者は The level ancestor problem simplified^[1] などに載っています。オンラインの方は実装がやや大変だと競プロ界隈では思われていがちです。

---

実装例

• オフライン版：提出 #56852439
  • ここでは、一般のオフライン線形時間 LA ではなく、この問題用のクエリを想定して楽をしています。
• オンライン版：がんばり中 → 書けました 提出 #56875669

（余談）特に添字が複雑になる部分については、実装例を見ながら写経しようとするのではなく、自分で手を動かす訓練をするのがよいでしょう。コンテスト本番でそういう問題が出たときのための訓練にもなります。

解説と実装例で細部が完全に一致しているわけではない（たとえば解説では問題文と合わせて 1-indexed だが実装では 0-indexed であるなど）ので、ご承知おきください。 実際には、0-indexed で実装する場合は考察の段階でも 0-indexed で詰めていくのがよいでしょう。

参考文献

[1]: Bender, Michael A., and Martın Farach-Colton. “The level ancestor problem simplified.” Theoretical Computer Science 321, no. 1 (2004): 5–12.

日本語解説記事もあります。 Level Ancestor Problem - 37zigenのHP