E - 社内連絡網 / Internal Contact Network Editorial by admin
Claude 4.6 Opus (Thinking)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
Preprocessing
- Compute Euler tour order (tin) and depth of each node via DFS
- Build LCA table using Binary Lifting (\(O(N \log N)\))
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.