概要

根付き木上で指定された社員集合のLCAを求め、LCAから各社員への距離の合計を計算する問題。さらに、1人を除外したときの距離合計の最小値も求める。

考察

重要な気づき 1：距離の計算を簡略化する

進行役 \(r = \mathrm{LCA}(S)\) は集合 \(S\) の全員の祖先であるため、\(r\) から \(V_i\) への距離は単純に深さの差で表せます：

\[\mathrm{dist}(r, V_i) = \mathrm{depth}(V_i) - \mathrm{depth}(r)\]

したがって値1は：

\[\sum_{i=1}^{K} \mathrm{dist}(r, V_i) = \sum_{i=1}^{K} \mathrm{depth}(V_i) - K \cdot \mathrm{depth}(r)\]

これにより、個々の距離をLCA計算なしで \(O(1)\) で合計を求められます。

重要な気づき 2：1人除外時のLCAを効率的に求める

値2を素朴に計算すると、各 \(t\) について残りの \(K-1\) 人のLCAを \(O(K \log N)\) で求めることになり、全体で \(O(K^2 \log N)\) かかります。

これを回避するために前方・後方LCA配列を使います： - \(\mathrm{prefix\_lca}[i]\)：\(V[0], V[1], \ldots, V[i]\) のLCA - \(\mathrm{suffix\_lca}[i]\)：\(V[i], V[i+1], \ldots, V[K-1]\) のLCA

\(V[t]\) を除いたときのLCAは： $\(\mathrm{LCA}(\mathrm{prefix\_lca}[t-1],\ \mathrm{suffix\_lca}[t+1])\)$

で \(O(\log N)\) で求まります。

重要な気づき 3：オイラーツアー順のソート

集合のLCAを求める際、ノードをオイラーツアーの訪問順（DFS順）でソートしておくと、隣接ペアのLCAを順に取ることで全体のLCAが正しく求まります。

アルゴリズム

1. 前処理

   • DFS でオイラーツアー順（tin）と各ノードの深さを求める
   • ダブリング（Binary Lifting）でLCAテーブルを構築（\(O(N \log N)\)）

2. 各クエリの処理

   • 招集社員を tin 順にソート
   • 全体のLCA \(r\) を累積的に計算
   • 値1を \(\sum \mathrm{depth}(V_i) - K \cdot \mathrm{depth}(r)\) で計算
   • 前方・後方LCA配列を構築
   • 各 \(t\) について、\(V[t]\) を除いた場合のLCA \(r'\) を求め、コスト \((\sum \mathrm{depth}(V_i) - \mathrm{depth}(V[t])) - (K-1) \cdot \mathrm{depth}(r')\) を計算
   • コストの最小値が値2

計算量

• 時間計算量: \(O(N \log N + \sum K_j \cdot \log N)\)
  • 前処理にダブリングテーブル構築で \(O(N \log N)\)
  • 各クエリでソート \(O(K_j \log K_j)\)、prefix/suffix LCA構築と各除外候補の計算に \(O(K_j \log N)\)
• 空間計算量: \(O(N \log N)\)（ダブリングテーブル分）

実装のポイント

• 距離を深さの差に変換：LCAが全員の祖先であることを利用して、\(\mathrm{dist}(r, v) = \mathrm{depth}(v) - \mathrm{depth}(r)\) とする。これが最大の高速化。

• prefix/suffix LCA：1人除外のLCAを \(O(\log N)\) で求める定番テクニック。配列の境界（\(t=0\) や \(t=K-1\)）に注意。

• \(K=1\) の特殊ケース：値1は0、値2は-1を返す。

• イテレーティブDFS：Pythonでは再帰の深さ制限があるため、スタックを使った反復DFSでオイラーツアーを構築する。

  ソースコード

import sys
from math import log2

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    
    N, Q = int(input_data[0]), int(input_data[1])
    idx = 2
    
    # Build tree
    parent = [0] * (N + 1)
    children = [[] for _ in range(N + 1)]
    for i in range(2, N + 1):
        p = int(input_data[idx]); idx += 1
        parent[i] = p
        children[p].append(i)
    
    # BFS to get euler tour and depth
    LOG = max(1, (N).bit_length())
    depth = [0] * (N + 1)
    
    # Euler tour
    tin = [0] * (N + 1)
    tout = [0] * (N + 1)
    timer = 0
    
    # Iterative DFS for euler tour
    stack = [(1, False)]
    while stack:
        node, visited = stack.pop()
        if visited:
            tout[node] = timer - 1
        else:
            tin[node] = timer
            timer += 1
            stack.append((node, True))
            for c in reversed(children[node]):
                depth[c] = depth[node] + 1
                stack.append((c, False))
    
    # Binary lifting for LCA
    up = [[0] * (N + 1) for _ in range(LOG)]
    up[0] = parent[:]
    up[0][1] = 1
    for k in range(1, LOG):
        for v in range(1, N + 1):
            up[k][v] = up[k-1][up[k-1][v]]
    
    def lca(u, v):
        if depth[u] < depth[v]:
            u, v = v, u
        diff = depth[u] - depth[v]
        for k in range(LOG):
            if (diff >> k) & 1:
                u = up[k][u]
        if u == v:
            return u
        for k in range(LOG - 1, -1, -1):
            if up[k][u] != up[k][v]:
                u = up[k][u]
                v = up[k][v]
        return up[0][u]
    
    def dist(u, v):
        l = lca(u, v)
        return depth[u] + depth[v] - 2 * depth[l]
    
    # For each query, we need to compute LCA of a set efficiently
    # Sort by euler tour order, LCA of set = LCA of consecutive pairs
    
    def lca_of_set(nodes):
        # Sort by tin
        nodes_sorted = sorted(nodes, key=lambda x: tin[x])
        result = nodes_sorted[0]
        for i in range(1, len(nodes_sorted)):
            result = lca(result, nodes_sorted[i])
        return result
    
    out = []
    
    for _ in range(Q):
        K = int(input_data[idx]); idx += 1
        V = []
        for i in range(K):
            V.append(int(input_data[idx])); idx += 1
        
        if K == 1:
            out.append("0 -1")
            continue
        
        # Sort V by euler tour
        V.sort(key=lambda x: tin[x])
        
        # Compute LCA of full set
        r = V[0]
        for i in range(1, K):
            r = lca(r, V[i])
        
        # Value 1: sum of dist(r, V[i])
        sum_depth_V = sum(depth[v] for v in V)
        val1 = sum_depth_V - K * depth[r]
        
        # Value 2: for each t, remove V[t], compute LCA of rest, then sum of distances
        # Prefix and suffix LCA
        prefix_lca = [0] * K
        suffix_lca = [0] * K
        prefix_lca[0] = V[0]
        for i in range(1, K):
            prefix_lca[i] = lca(prefix_lca[i-1], V[i])
        suffix_lca[K-1] = V[K-1]
        for i in range(K-2, -1, -1):
            suffix_lca[i] = lca(suffix_lca[i+1], V[i])
        
        min_val2 = float('inf')
        for t in range(K):
            # LCA of V without V[t]
            if t == 0:
                r2 = suffix_lca[1]
            elif t == K - 1:
                r2 = prefix_lca[K - 2]
            else:
                r2 = lca(prefix_lca[t - 1], suffix_lca[t + 1])
            
            # sum of dist(r2, V[i]) for i != t
            # = sum(depth[V[i]] for i!=t) - (K-1)*depth[r2]
            cost = (sum_depth_V - depth[V[t]]) - (K - 1) * depth[r2]
            if cost < min_val2:
                min_val2 = cost
        
        out.append(f"{val1} {min_val2}")
    
    sys.stdout.write("\n".join(out) + "\n")

main()

---

この解説は claude4.6opus-thinking によって生成されました。