概要

この問題は、木構造（会社の組織図）において指定された \(K\) 人の社員（頂点）の集合に対し、以下の2つの値を効率よく求める問題です。

• 値 1：全員の最小共通祖先（LCA）から、各メンバーへの距離の総和。
• 値 2：メンバーからちょうど1人を除外したときの、新たなLCAから残ったメンバーへの距離の総和の最小値。

木上の距離とLCA（最小共通祖先）の性質を巧みに利用することで、各クエリに対して高速に解答を求めることができます。

---

考察

1. 距離の総和の式変形

木上の2頂点 \(u, v\) の距離は、根（社員1）からの深さ \(\mathrm{depth}\) と、2頂点の最小共通祖先 \(\mathrm{LCA}(u, v)\) を用いて以下のように表せます。

\[\mathrm{dist}(u, v) = \mathrm{depth}(u) + \mathrm{depth}(v) - 2 \cdot \mathrm{depth}(\mathrm{LCA}(u, v))\]

今、招集されたメンバーの集合を \(S\)、そのLCAを \(r = \mathrm{LCA}(S)\) とします。 \(r\) は \(S\) に含まれるすべての頂点の祖先であるため、任意の \(v \in S\) に対して \(\mathrm{LCA}(r, v) = r\) が成り立ちます。

したがって、値 1 である「\(r\) から各メンバーへの距離の総和」は以下のように変形できます。

\[\sum_{v \in S} \mathrm{dist}(r, v) = \sum_{v \in S} (\mathrm{depth}(v) - \mathrm{depth}(r)) = \left( \sum_{v \in S} \mathrm{depth}(v) \right) - |S| \cdot \mathrm{depth}(r)\]

メンバー全員の深さの総和を \(D = \sum_{v \in S} \mathrm{depth}(v)\)、メンバー数を \(K = |S|\) とおくと、値 1 は \(D - K \cdot \mathrm{depth}(r)\) と非常にシンプルな式で計算できます。

2. 1人除外したときの最小化（値 2）

同様に、あるメンバー \(t \in S\) を1人除外したときの距離の総和を考えます。 残った集合 \(S \setminus \{t\}\) のLCAを \(r'\) とすると、その距離の総和は以下のようになります。

\[\sum_{v \in S \setminus \{t\}} \mathrm{dist}(r', v) = \left( \sum_{v \in S \setminus \{t\}} \mathrm{depth}(v) \right) - (K - 1) \cdot \mathrm{depth}(r')\]

ここで、 \(\sum_{v \in S \setminus \{t\}} \mathrm{depth}(v) = D - \mathrm{depth}(t)\) であるため、上の式は次のように整理できます。

\[D - \left[ \mathrm{depth}(t) + (K - 1) \cdot \mathrm{depth}(r') \right]\]

\(D\) は除外する人によらず一定なので、この値（距離の総和）を最小化するためには、引き算している部分である

\[g(t) = \mathrm{depth}(t) + (K - 1) \cdot \mathrm{depth}(\mathrm{LCA}(S \setminus \{t\}))\]

を最大化すればよいことになります。

3. LCAの重要な性質とDFS順（行きがけ順）

素朴にすべての \(t \in S\) について \(\mathrm{LCA}(S \setminus \{t\})\) を求め直すと、1クエリあたり \(O(K^2 \log N)\) などの時間がかかり、実行時間制限に間に合いません（TLE）。そこで、LCAに関する強力な性質を利用します。

【LCAの性質】 木をDFS（深さ優先探索）したときの行きがけ順（tin と呼びます）で頂点集合 \(S\) をソートし、 \(V_1, V_2, \ldots, V_K\) と並べたとき、集合全体のLCAは、最も tin が小さい頂点 \(V_1\) と、最も tin が大きい頂点 \(V_K\) のLCAに一致する。

\[\mathrm{LCA}(S) = \mathrm{LCA}(V_1, V_K)\]

この性質を用いると、除外する頂点 \(t\) に応じて、残された集合のLCA \(r' = \mathrm{LCA}(S \setminus \{t\})\) は以下の3つのケースに分類できます。

1. \(t = V_1\) （tin が最小の頂点）を除外する場合 残った集合の中で tin が最小になるのは \(V_2\)、最大なのは \(V_K\) です。 したがって、新たなLCAは \(r' = \mathrm{LCA}(V_2, V_K)\) となります。
2. \(t = V_K\) （tin が最大の頂点）を除外する場合 残った集合の中で tin が最小になるのは \(V_1\)、最大なのは \(V_{K-1}\) です。 したがって、新たなLCAは \(r' = \mathrm{LCA}(V_1, V_{K-1})\) となります。
3. それ以外の \(t \in \{V_2, \ldots, V_{K-1}\}\) を除外する場合 残った集合の tin の最小値は \(V_1\)、最大値は \(V_K\) のまま変わりません。 したがって、新たなLCAは元のLCAと変わらず \(r' = r = \mathrm{LCA}(V_1, V_K)\) となります。

4. 高速化のまとめ

ケース3において、LCAは常に元の \(r\) のままで一定です。 したがって、ケース3の中で \(g(t) = \mathrm{depth}(t) + (K - 1) \cdot \mathrm{depth}(r)\) を最大化するためには、\(V_2, \ldots, V_{K-1}\) の中で最も深さ \(\mathrm{depth}(t)\) が大きい頂点を選べばよいことになります。

これにより、調べるべき除外候補 \(t\) は以下の最大3通りに絞られます！

• 候補①： \(t = V_1\)
• 候補②： \(t = V_K\)
• 候補③： \(V_2, \ldots, V_{K-1}\) のうち、最も \(\mathrm{depth}\) が大きい頂点（\(K > 2\) のときのみ）

これら3つの候補に対して \(g(t)\) を計算し、その最大値を \(D\) から引くことで、値 2 を \(O(\log N + K)\) で求めることができます。

---

アルゴリズム

1. 前処理（木全体の情報取得）

   • 与えられた親の関係から隣接リストを構築します。
   • DFS（またはBFS）を行い、各頂点 \(i\) の根からの深さ depth[i] と、DFSでの行きがけ順 tin[i] を求めます。
   • ダブリング（Doubling）を用いて、2頂点のLCAを \(O(\log N)\) で求めるためのテーブル parent[i][d] （頂点 \(i\) の \(2^d\) 個上の祖先）を構築します。

2. クエリ処理 各クエリで与えられた頂点集合 \(V\) に対して以下を行います。

   • \(K = 1\) の場合は、値 1 = 0、値 2 = -1 を出力して次のクエリへ。
   • 集合 \(V\) を tin の値が小さい順にソートします。ソート後の配列を \(V = [V_0, V_1, \ldots, V_{K-1}]\) とします（0-indexed）。
   • 全体のLCA \(r = \mathrm{LCA}(V_0, V_{K-1})\) を求めます。
   • 全体の深さの総和 \(D = \sum_{v \in V} \mathrm{depth}(v)\) を求めます。
   • 値 1 を \(D - K \cdot \mathrm{depth}(r)\) として計算します。
   • 値 2 を求めるため、以下の3つの候補から \(g(t)\) の最大値を求めます。
     1. \(t = V_0\) のとき： \(g_1 = \mathrm{depth}(V_0) + (K-1) \cdot \mathrm{depth}(\mathrm{LCA}(V_1, V_{K-1}))\)
     2. \(t = V_{K-1}\) のとき： \(g_2 = \mathrm{depth}(V_{K-1}) + (K-1) \cdot \mathrm{depth}(\mathrm{LCA}(V_0, V_{K-2}))\)
     3. \(K > 2\) のとき、中間メンバー \(V_1, \ldots, V_{K-2}\) の中での最大深さを \(M\) とし、 \(g_3 = M + (K-1) \cdot \mathrm{depth}(r)\)
   • \(g_1, g_2, g_3\) の最大値を \(g_{\max}\) としたとき、値 2 は \(D - g_{\max}\) となります。

---

計算量

時間計算量

• 前処理: \(O(N \log N)\)
  • DFSによる depth, tin の計算に \(O(N)\)。
  • ダブリングテーブルの構築に \(O(N \log N)\)（深さの最大が \(18\) 程度なので、定数倍も非常に小さいです）。
• クエリ処理: \(O(\sum K \log K + Q \log N)\)
  • 各クエリにおいて、 \(K\) 個の要素のソートに \(O(K \log K)\)。
  • LCAの計算（高々3回）に \(O(\log N)\)。
  • 中間メンバーの最大深さの探索に \(O(K)\)。
  • 全クエリの \(K\) の総和は \(\sum K \le 2 \times 10^5\) であるため、制限時間内に余裕で間に合います。

空間計算量

• \(O(N \log N)\)
  • ダブリング用のテーブル parent（サイズ \(N \times 18\)）が支配的です。

---

実装のポイント

• 再帰の回避（Python高速化） Pythonにおいて再帰関数によるDFSを行うと、コールスタックのオーバーヘッドや再帰回数制限（sys.setrecursionlimit）の問題が発生します。 本コードでは、明示的なスタック（while stack:）を用いた非再帰のDFSを実装することで、高速かつ安全に行きがけ順 tin を求めています。

• 高速な入出力 クエリ数が多く入力の行数も多いため、sys.stdin.read().split() を用いて入力を一括で取得し、処理を高速化しています。

  ソースコード

import sys

def solve():
    # 入力を一括で読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    Q = int(input_data[1])
    
    P = [int(x) for x in input_data[2:N+1]]
    
    # 隣接リストの構築
    adj = [[] for _ in range(N + 1)]
    for i in range(2, N + 1):
        adj[P[i - 2]].append(i)
        
    depth = [0] * (N + 1)
    parent = [[0] * 18 for _ in range(N + 1)]
    
    parent[1][0] = 1
    for i in range(2, N + 1):
        p = P[i - 2]
        depth[i] = depth[p] + 1
        parent[i][0] = p
        
    # ダブリングテーブルの構築
    for d in range(17):
        for i in range(1, N + 1):
            parent[i][d+1] = parent[parent[i][d]][d]
            
    # DFS順 tin の計算
    tin = [0] * (N + 1)
    timer = 0
    stack = [1]
    while stack:
        u = stack.pop()
        timer += 1
        tin[u] = timer
        for v in reversed(adj[u]):
            stack.append(v)
            
    R18 = list(range(18))
    REV18 = list(reversed(range(18)))
    
    # LCAを求める関数
    def get_lca(u, v):
        if depth[u] < depth[v]:
            u, v = v, u
        diff = depth[u] - depth[v]
        pu = parent[u]
        for d in R18:
            if (diff >> d) & 1:
                u = pu[d]
                pu = parent[u]
        if u == v:
            return u
        pu = parent[u]
        pv = parent[v]
        for d in REV18:
            if pu[d] != pv[d]:
                u = pu[d]
                v = pv[d]
                pu = parent[u]
                pv = parent[v]
        return pu[0]
        
    idx = N + 1
    out = []
    for _ in range(Q):
        K = int(input_data[idx])
        V = [int(x) for x in input_data[idx+1 : idx+1+K]]
        idx += 1 + K
        
        if K == 1:
            out.append("0 -1")
            continue
            
        # tin の昇順にソート
        V.sort(key=lambda x: tin[x])
        
        v1 = V[0]
        vK = V[-1]
        
        r = get_lca(v1, vK)
        D = sum(depth[x] for x in V)
        
        ans1 = D - K * depth[r]
        
        # 候補1: v1 を除外
        v2 = V[1]
        lca_ex1 = get_lca(v2, vK)
        g1 = depth[v1] + (K - 1) * depth[lca_ex1]
        
        # 候補2: vK を除外
        vK_minus_1 = V[-2]
        lca_exK = get_lca(v1, vK_minus_1)
        g2 = depth[vK] + (K - 1) * depth[lca_exK]
        
        max_g = g1 if g1 > g2 else g2
        
        # 候補3: それ以外の頂点を除外
        if K > 2:
            max_dep_mid = max(depth[x] for x in V[1:-1])
            g3 = max_dep_mid + (K - 1) * depth[r]
            if g3 > max_g:
                max_g = g3
                
        ans2 = D - max_g
        out.append(f"{ans1} {ans2}")
        
    print('\n'.join(out))

if __name__ == '__main__':
    solve()

---

この解説は gemini-3.5-flash-thinking によって生成されました。