Overview

Given a rooted tree representing a boss-subordinate relationship, for each query we find the LCA of a specified set of employees, then efficiently compute the sum of distances from the LCA to each employee (value 1) and the minimum sum of distances when one person is excluded (value 2).

Key Observations

Key Insight 1: The sum of distances from the LCA can be expressed using only “depths”

Let the set given in a query be \(S=\{v_1,\dots,v_K\}\) and let \(r=\mathrm{LCA}(S)\).
Since \(r\) is an ancestor of all members, for each \(v\):

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

holds (from \(r\) to \(v\) we only go downward).

Therefore, value 1 is:

\[ \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) \]

This means it can be computed using only “the sum of depths of all points” and “the depth of the LCA.”

---

Key Insight 2: For value 2, we need to try removing each person and computing the LCA of the remaining set

Value 2 requires trying all \(K\) choices of “who to exclude,” and for each:

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

then taking the minimum.

Naively recomputing the LCA each time would require: - \(O(K)\) LCA computations per candidate \(t\) → total \(O(K^2)\) per query

which is too slow even when \(\sum K \le 2\times 10^5\) in the worst case.

---

Solution: Use prefix/suffix to compute “LCA with one person removed” in \(O(\log N)\)

For the array \(v_1,\dots,v_K\), define:

• 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)\)

Then the LCA of the remaining elements after removing \(v_{i+1}\) (or \(v_i\) in 0-indexed) is:

• Edge cases:
  
  • \(i=0\) (remove the first element): \(\mathrm{LCA}(v_2,\dots,v_K)=\text{suf}[1]\)
  • \(i=K-1\) (remove the last element): \(\mathrm{LCA}(v_1,\dots,v_{K-1})=\text{pre}[K-2]\)
• Middle case:
  
  • \(\mathrm{LCA}(v_1,\dots,v_i, v_{i+2},\dots,v_K)=\mathrm{LCA}(\text{pre}[i-1], \text{suf}[i+1])\)

After that, the distance sum can be computed using only depths, just like value 1.

Algorithm

1. Preprocessing (Speeding up LCA)

Use Binary Lifting to enable \(O(\log N)\) LCA queries.

• \(\text{up}[k][v]\): the ancestor \(2^k\) levels above vertex \(v\)
• Compute \(\mathrm{depth}(v)\) simultaneously

LCA\((a,b)\) is computed by: 1. Lifting the deeper node to the same depth as the shallower one 2. Comparing ancestors from the top and lifting both nodes to just below the branching point

---

2. Processing Each Query

Let the \(K\) people given in a query be \(v_1,\dots,v_K\), and let \(D=\sum_{i=1}^K \mathrm{depth}(v_i)\).

Value 1

1. Compute \(r=\mathrm{LCA}(v_1,\dots,v_K)\) using the prefix LCA (\(\text{pre}[K-1]\))
2. \(\text{val1} = D - K\cdot \mathrm{depth}(r)\)

Value 2 (output \(-1\) if \(K=1\))

1. Also build the suffix LCA
2. For each \(i\), compute the LCA \(r_i'\) when “\(v_i\) is excluded” using prefix/suffix
3. The sum of depths of the remaining members is \(D-\mathrm{depth}(v_i)\), so the distance sum is:

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

1. \(\min_i \text{cost}_i\) is value 2

---

(Small Example)

For example, when \(K=4\) with \(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)]\)

If we remove \(v_3\), the remaining set is \((v_1,v_2,v_4)\), so
\(\mathrm{LCA}(v_1,v_2,v_4)=\mathrm{LCA}(\text{pre}[1],\text{suf}[3])\).

Complexity

• Time complexity:
  
  • Preprocessing (building the up table): \(O(N\log N)\)
    
  • Each query: building prefix/suffix and computing each candidate in \(O(K\log N)\)
    
  • Overall: \(O\bigl((N+\sum K)\log N\bigr)\)
• Space complexity: \(O(N\log N)\) (for the up table and depth array)

Implementation Notes

• For both value 1 and value 2, do not directly sum distances. Always reduce to
  \(\mathrm{dist}(r,v)=\mathrm{depth}(v)-\mathrm{depth}(r)\)
  and compute as “sum of depths \(-\) number of people \(\times\) depth of LCA.”

• For value 2, instead of recomputing the “LCA with one person removed” from scratch each time, use the prefix/suffix combination to achieve \(O(\log N)\).

• Since the input size is large, use sys.stdin.buffer.read() for bulk reading to speed up I/O.

  Source Code

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

---

This editorial was generated by gpt-5.2-high.