概要

上司関係が根付き木で与えられるとき、各クエリで指定された社員集合の LCA を求め、LCA から各社員までの距離和（値1）と、1人欠席させた場合の最小距離和（値2）を高速に計算します。

考察

重要な気づき 1：LCA からの距離和は「深さ」だけで書ける

クエリで与えられた集合を \(S=\{v_1,\dots,v_K\}\) とし、\(r=\mathrm{LCA}(S)\) とします。
\( r \) は全員の祖先なので、各 \(v\) について

• \(\mathrm{dist}(r,v)=\mathrm{depth}(v)-\mathrm{depth}(r)\)

が成り立ちます（\(r\) から \(v\) へは下に降りるだけ）。

したがって値1は

\[ \sum_{i=1}^{K}\mathrm{dist}(r,v_i) =\sum_{i=1}^{K}\bigl(\mathrm{depth}(v_i)-\mathrm{depth}(r)\bigr) =\Bigl(\sum_{i=1}^{K}\mathrm{depth}(v_i)\Bigr)-K\cdot \mathrm{depth}(r) \]

となり、「各点の深さの総和」と「LCA の深さ」だけで求まります。

---

重要な気づき 2：値2は「1人除いた集合の LCA」を全員分試す必要がある

値2は「誰を欠席させるか」の \(K\) 通りを試し、そのときの

• \(r'=\mathrm{LCA}(S\setminus\{v_t\})\)
• 距離和 \(\sum_{i\neq t}\mathrm{dist}(r',v_i)\)

の最小を取ります。

素朴に毎回 LCA を取り直すと、1回のクエリで - 各候補 \(t\) ごとに LCA 計算が \(O(K)\) 回必要 → 合計 \(O(K^2)\) となり、\(\sum K \le 2\times 10^5\) でも最悪で間に合いません。

---

解決策：prefix/suffix で「1人除いた LCA」を \(O(\log N)\) で出す

配列 \(v_1,\dots,v_K\) に対して

• prefix LCA：\(\text{pre}[i]=\mathrm{LCA}(v_1,\dots,v_{i+1})\)
• suffix LCA：\(\text{suf}[i]=\mathrm{LCA}(v_{i+1},\dots,v_K)\)

を作ると、\(v_{i+1}\)（0-indexなら \(v_i\)）を除いた残りの LCA は

• 端の場合
  
  • \(i=0\)（先頭を除く）：\(\mathrm{LCA}(v_2,\dots,v_K)=\text{suf}[1]\)
  • \(i=K-1\)（末尾を除く）：\(\mathrm{LCA}(v_1,\dots,v_{K-1})=\text{pre}[K-2]\)
• 中央の場合
  
  • \(\mathrm{LCA}(v_1,\dots,v_i, v_{i+2},\dots,v_K)=\mathrm{LCA}(\text{pre}[i-1], \text{suf}[i+1])\)

で求まります。あとは値1と同様に深さだけで距離和が出せます。

アルゴリズム

1. 前処理（LCA を高速化）

二分累乗（Binary Lifting）で LCA を \(O(\log N)\) で求められるようにします。

• \(\text{up}[k][v]\)：頂点 \(v\) の \(2^k\) 個上の祖先
• 深さ \(\mathrm{depth}(v)\) も同時に計算

LCA\((a,b)\) は 1. 深い方を同じ深さまで持ち上げる 2. 上から順に祖先を比べ、分岐直前まで両方を持ち上げる で求めます。

---

2. 各クエリの処理

クエリで与えられた \(K\) 人を \(v_1,\dots,v_K\) とし、\(D=\sum_{i=1}^K \mathrm{depth}(v_i)\) とします。

値1

1. \(r=\mathrm{LCA}(v_1,\dots,v_K)\) を prefix LCA で求める（\(\text{pre}[K-1]\)）
2. \( \text{val1} = D - K\cdot \mathrm{depth}(r)\)

値2（\(K=1\) は \(-1\)）

1. suffix LCA も作る
2. 各 \(i\) について「\(v_i\) を欠席」したときの LCA \(r_i'\) を prefix/suffix から求める
3. 残りの深さ総和は \(D-\mathrm{depth}(v_i)\) なので距離和は

\[ \text{cost}_i = (D-\mathrm{depth}(v_i)) - (K-1)\cdot \mathrm{depth}(r_i') \]

1. \(\min_i \text{cost}_i\) が値2

---

（小例）

例えば \(K=4\)、\(v_1,v_2,v_3,v_4\) のとき
- pre：\([\mathrm{LCA}(v_1),\ \mathrm{LCA}(v_1,v_2),\ \mathrm{LCA}(v_1,v_2,v_3),\ \mathrm{LCA}(v_1,v_2,v_3,v_4)]\) - suf：\([\mathrm{LCA}(v_1,v_2,v_3,v_4),\ \mathrm{LCA}(v_2,v_3,v_4),\ \mathrm{LCA}(v_3,v_4),\ \mathrm{LCA}(v_4)]\)

\(v_3\) を除くなら残りは \((v_1,v_2,v_4)\) なので
\(\mathrm{LCA}(v_1,v_2,v_4)=\mathrm{LCA}(\text{pre}[1],\text{suf}[3])\) となります。

計算量

• 時間計算量:
  
  • 前処理（up テーブル構築）: \(O(N\log N)\)
    
  • 各クエリ: prefix/suffix 作成と各候補の計算で \(O(K\log N)\)
    
  • 全体: \(O\bigl((N+\sum K)\log N\bigr)\)
• 空間計算量: \(O(N\log N)\)（up テーブルと深さ配列）

実装のポイント

• 値1・値2ともに距離を直接足さず、必ず
  \( \mathrm{dist}(r,v)=\mathrm{depth}(v)-\mathrm{depth}(r)\)
  に落として「深さの和 \(-\) 人数 \(\times\) LCAの深さ」で計算します。

• 値2は「1人除いた LCA」を毎回作り直さず、prefix/suffix の組み合わせで \(O(\log N)\) にします。

• 入力サイズが大きいので、sys.stdin.buffer.read() による一括読み取りで高速化しています。

  ソースコード

import sys
from array import array

def main():
    it = iter(map(int, sys.stdin.buffer.read().split()))
    N = next(it)
    Q = next(it)

    LOG = (N).bit_length()
    depth = array('I', [0]) * (N + 1)

    up = [array('I', [0]) * (N + 1) for _ in range(LOG)]
    up0 = up[0]

    for v in range(2, N + 1):
        p = next(it)
        up0[v] = p
        depth[v] = depth[p] + 1

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

    rev_levels = list(range(LOG - 1, -1, -1))

    def lca(a, b):
        da = depth[a]
        db = depth[b]
        if da < db:
            a, b = b, a
            da, db = db, da

        diff = da - db
        bit = 0
        while diff:
            if diff & 1:
                a = up[bit][a]
            diff >>= 1
            bit += 1

        if a == b:
            return a

        for k in rev_levels:
            ua = up[k][a]
            ub = up[k][b]
            if ua != ub:
                a = ua
                b = ub
        return up0[a]

    out_lines = []
    for _ in range(Q):
        K = next(it)
        vs = [0] * K
        total_depth = 0
        for i in range(K):
            v = next(it)
            vs[i] = v
            total_depth += depth[v]

        # prefix LCA (also gives overall LCA)
        pre = [0] * K
        pre[0] = vs[0]
        for i in range(1, K):
            pre[i] = lca(pre[i - 1], vs[i])
        r = pre[-1]
        val1 = total_depth - K * depth[r]

        if K == 1:
            out_lines.append(f"{val1} -1")
            continue

        suf = [0] * K
        suf[-1] = vs[-1]
        for i in range(K - 2, -1, -1):
            suf[i] = lca(suf[i + 1], vs[i])

        best = 10**30
        k1 = K - 1
        for i in range(K):
            if i == 0:
                rr = suf[1]
            elif i == K - 1:
                rr = pre[K - 2]
            else:
                rr = lca(pre[i - 1], suf[i + 1])
            cost = (total_depth - depth[vs[i]]) - k1 * depth[rr]
            if cost < best:
                best = cost

        out_lines.append(f"{val1} {best}")

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

if __name__ == "__main__":
    main()

---

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