Overview

A problem where you find the LCA of a specified set of employees on a rooted tree, calculate the total distance from the LCA to each employee, and also find the minimum total distance when excluding one person.

Key Observations

Key Insight 1: Simplifying Distance Calculation

Since the moderator \(r = \mathrm{LCA}(S)\) is an ancestor of everyone in set \(S\), the distance from \(r\) to \(V_i\) can be simply expressed as the difference in depths:

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

Therefore, Value 1 is:

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

This allows us to compute the total in \(O(1)\) without calculating individual distances via LCA.

Key Insight 2: Efficiently Finding LCA When Excluding One Person

If we naively compute Value 2, for each \(t\) we would need to find the LCA of the remaining \(K-1\) people in \(O(K \log N)\), resulting in \(O(K^2 \log N)\) overall.

To avoid this, we use prefix/suffix LCA arrays: - \(\mathrm{prefix\_lca}[i]\): LCA of \(V[0], V[1], \ldots, V[i]\) - \(\mathrm{suffix\_lca}[i]\): LCA of \(V[i], V[i+1], \ldots, V[K-1]\)

The LCA when excluding \(V[t]\) is: $\(\mathrm{LCA}(\mathrm{prefix\_lca}[t-1],\ \mathrm{suffix\_lca}[t+1])\)$

which can be computed in \(O(\log N)\).

Key Insight 3: Sorting by Euler Tour Order

When finding the LCA of a set, if the nodes are sorted by Euler tour visit order (DFS order), the overall LCA can be correctly obtained by sequentially taking the LCA of adjacent pairs.

Algorithm

1. Preprocessing

   • Compute Euler tour order (tin) and depth of each node via DFS
   • Build LCA table using Binary Lifting (\(O(N \log N)\))

2. Processing Each Query

   • Sort the summoned employees by tin order
   • Compute the overall LCA \(r\) cumulatively
   • Calculate Value 1 as \(\sum \mathrm{depth}(V_i) - K \cdot \mathrm{depth}(r)\)
   • Build prefix/suffix LCA arrays
   • For each \(t\), find the LCA \(r'\) when excluding \(V[t]\), and compute the cost \((\sum \mathrm{depth}(V_i) - \mathrm{depth}(V[t])) - (K-1) \cdot \mathrm{depth}(r')\)
   • The minimum cost is Value 2

Complexity

• Time complexity: \(O(N \log N + \sum K_j \cdot \log N)\)
  • Preprocessing: building the binary lifting table in \(O(N \log N)\)
  • Per query: sorting in \(O(K_j \log K_j)\), prefix/suffix LCA construction and computation for each exclusion candidate in \(O(K_j \log N)\)
• Space complexity: \(O(N \log N)\) (for the binary lifting table)

Implementation Notes

• Converting distance to depth difference: Leveraging the fact that the LCA is an ancestor of everyone, we use \(\mathrm{dist}(r, v) = \mathrm{depth}(v) - \mathrm{depth}(r)\). This is the biggest speedup.

• Prefix/Suffix LCA: A standard technique to find the LCA excluding one person in \(O(\log N)\). Be careful with boundary cases (\(t=0\) or \(t=K-1\)).

• Special case \(K=1\): Value 1 is 0, Value 2 returns -1.

• Iterative DFS: In Python, due to recursion depth limits, build the Euler tour using iterative DFS with an explicit stack.

  Source Code

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()

---

This editorial was generated by claude4.6opus-thinking.