概要

この問題は、根付き木に対して複数回の「2 頂点の最も深い共通の上司」を求める問題です。
これは木における LCA（Lowest Common Ancestor, 最小共通祖先） を求める典型問題で、ダブリングを使うと高速に処理できます。

考察

求めたいのは、社員 \(X, Y\) の両方の上司である社員のうち、最も深いものです。
木構造でいうと、これはちょうど \(X\) と \(Y\) の LCA にあたります。

素朴な方法

たとえば各問い合わせごとに

• 深い方の頂点を上に持ち上げて深さをそろえる
• その後、両方を 1 つずつ親へ進める

という方法でも答えは求まります。

しかし、この方法だと最悪で 1 回の問い合わせにつき \(O(N)\) かかります。
制約は

• \(N \le 3 \times 10^5\)
• \(Q \le 5 \times 10^4\)

なので、最悪 \(O(NQ)\) になり、これは間に合いません。

重要な気づき

「親を 1 回ずつたどる」のではなく、
\(2^0, 2^1, 2^2, \dots\) 個上の祖先を前計算しておけば、一気に上へジャンプできます。

たとえば、

• up[0][v]: 頂点 \(v\) の 1 個上の親
• up[1][v]: 頂点 \(v\) の 2 個上の祖先
• up[2][v]: 頂点 \(v\) の 4 個上の祖先
• …

のように持っておくと、深さ差を 2 進数で分解して \(O(\log N)\) で埋められます。

さらに、深さをそろえた後も、上から順に大きくジャンプしていけば、LCA の直前まで高速に近づけます。

この問題で嬉しい点

入力では \(P_i < i\) が保証されています。
つまり、社員 \(i\) の親は必ずそれより番号が小さいので、\(2\) から順に読めば

• 親の深さがすでに分かっている
• よって depth[i] = depth[p] + 1 とすぐ計算できる

という利点があります。
そのため、このコードでは DFS や BFS を使わずに深さを求めています。

アルゴリズム

1. 前計算

各頂点について

• depth[v]: 根からの深さ
• up[j][v]: 頂点 \(v\) の \(2^j\) 個上の祖先

を求めます。

まず親情報から

• up[0][i] = P_i
• depth[i] = depth[P_i] + 1

を計算します。

次にダブリング表を

\(up[j][v] = up[j-1][\,up[j-1][v]\,]\)

で埋めます。
これは「\(2^j\) 個上の祖先は、\(2^{j-1}\) 個上の祖先のさらに \(2^{j-1}\) 個上」と考えれば自然です。

---

2. 各問い合わせの処理

問い合わせ \((x, y)\) に対して LCA を求めます。

手順 1: 深さをそろえる

まず、深い方を上へ持ち上げて、\(x\) と \(y\) の深さを一致させます。

たとえば深さ差が 13 なら

\(13 = 8 + 4 + 1 = 2^3 + 2^2 + 2^0\)

なので、

• 8 個上
• 4 個上
• 1 個上

へジャンプすればよいです。

これをダブリング表で行うと \(O(\log N)\) です。

手順 2: すでに一致しているか確認

深さをそろえた時点で \(x = y\) なら、その頂点が答えです。
これは「片方がもう片方の上司だった」ケースに対応します。

手順 3: 2 頂点を同時に持ち上げる

まだ異なるなら、今度は大きいジャンプから順に見ていきます。

\(j\) を大きい方から小さい方へ見て、

• up[j][x] != up[j][y]

なら、まだ LCA より下にいるので、両方をその祖先まで持ち上げます。

これを繰り返すと、最後に \(x, y\) は LCA の 1 つ下の子 になります。
したがって答えは up[0][x]（または up[0][y]）です。

---

具体例

たとえば次のような木を考えます。

• \(1\) が根
• \(2, 3\) の親は \(1\)
• \(4, 5\) の親は \(2\)
• \(6, 7\) の親は \(3\)

このとき、

• \(LCA(4, 5) = 2\)
• \(LCA(4, 6) = 1\)
• \(LCA(2, 5) = 2\)

となります。

最後の例では、深さをそろえたあとに \(x = y\) になるので、そのまま答えが出ます。

計算量

• 時間計算量: 前計算が \(O(N \log N)\)、各問い合わせが \(O(\log N)\)、合計で \(O(N \log N + Q \log N)\)
• 空間計算量: \(O(N \log N)\)

実装のポイント

• LOG = N.bit_length() とすると、\(2^{LOG} > N\) となるので十分な段数を確保できます。

• 根である頂点 \(1\) の親は存在しませんが、この実装では 0 をダミーとして使っています。
  up[j][1] = 0 のままで問題ありません。

• この問題では \(P_i < i\) が保証されているため、depth[i] を入力順にそのまま計算できます。

• クエリ数・頂点数が大きいので、sys.stdin.buffer.read() を使って高速入力にしています。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)

    N = next(it)
    Q = next(it)

    LOG = N.bit_length()
    depth = [0] * (N + 1)
    up = [[0] * (N + 1) for _ in range(LOG)]

    for i in range(2, N + 1):
        p = next(it)
        up[0][i] = p
        depth[i] = depth[p] + 1

    for j in range(1, LOG):
        prev = up[j - 1]
        cur = up[j]
        for i in range(1, N + 1):
            cur[i] = prev[prev[i]]

    out = []
    for _ in range(Q):
        x = next(it)
        y = next(it)

        if depth[x] < depth[y]:
            x, y = y, x

        diff = depth[x] - depth[y]
        b = 0
        while diff:
            if diff & 1:
                x = up[b][x]
            diff >>= 1
            b += 1

        if x == y:
            out.append(str(x))
            continue

        for j in range(LOG - 1, -1, -1):
            if up[j][x] != up[j][y]:
                x = up[j][x]
                y = up[j][y]

        out.append(str(up[0][x]))

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

---

この解説は gpt-5.4-high によって生成されました。