E - 通信ネットワークの妨害 / Disruption of Communication Network 解説 by admin
gemini-3.5-flash-highSummary
This problem is a game played on a tree-structured communication network. Aoki first disconnects one link (or chooses not to disconnect any), after which Takahashi chooses an arbitrary base station and steals data from all base stations within distance \(D\) of his entry point, maximizing the stolen data. Aoki wants to minimize the maximum amount of data Takahashi can steal.
We can find the result when both players play optimally in \(O(N^2)\) using all-pairs shortest paths and cumulative sums, which is an application of Tree DP.
Analysis
1. Understanding the Game Structure
Aoki can disconnect at most one link (edge). Suppose he disconnects an edge \(e = (u, v)\) (where \(u\) is the parent of \(v\)). This splits the tree into two parts: - The subtree of vertex \(v\) (hereafter referred to as the IN side) - The remaining part of the tree (hereafter referred to as the OUT side)
Takahashi will optimally choose the base station (entry point) in the disconnected network to steal the maximum amount of data. - If Takahashi enters a vertex \(x\) on the IN side, let the maximum data he can obtain be \(M_{in}[v]\). - If Takahashi enters a vertex \(y\) on the OUT side, let the maximum data he can obtain be \(M_{out}[v]\).
Since Takahashi will choose the best entry point, the amount of data he steals when edge \((u, v)\) is disconnected is \(\max(M_{in}[v], M_{out}[v])\).
Aoki wants to minimize this value, so we compute this value for all edges and find the minimum. Since Aoki also has the option to “not disconnect any link”, the final answer will be the minimum of the above value over all edges and the maximum data Takahashi can obtain in the initial state (with no disconnections).
2. Naive Approach and Its Limitations
For each disconnected edge, if we run a BFS (Breadth-First Search) from every vertex to find the amount of data within distance \(D\), it takes \(O(N^2)\) per edge, leading to a total time complexity of \(O(N^3)\). For \(N \le 3000\), \(N^3 \approx 2.7 \times 10^{10}\), which will exceed the time limit (TLE).
3. Optimization Idea (Using Differences)
Let \(S_{all\_D}[i]\) be the total data amount within distance \(D\) from vertex \(i\) in the initial state (without any disconnections). This can be precomputed in \(O(N^2)\).
When edge \((u, v)\) is disconnected, if we can compute the “unreachable (subtracted) data amount” from a given vertex as a difference in \(O(1)\), we can simulate the disconnection of each edge much faster.
Algorithm
1. Preparation (Euler Tour and Shortest Paths)
- Build the tree with an arbitrary vertex (e.g., vertex \(0\)) as the root.
- Create a pre-order (topological order) array
order. This allows us to represent the set of vertices in the subtree of any vertex \(u\) as a contiguous interval \([L[u], R[u])\) inorder. - Compute the all-pairs shortest paths \(dist[u][v]\) in \(O(N^2)\) by running BFS from each vertex.
2. Defining Cumulative Sums
Precompute the following two cumulative sum tables in \(O(N^2)\):
- \(S_{all}[u][k]\) : The total data amount of all vertices within distance \(k\) from vertex \(u\).
- \(S_{in}[v][k]\) : The total data amount of vertices within the subtree of \(v\) (IN side) that are within distance \(k\) from vertex \(v\).
3. Calculating the Impact of Disconnection via Differences
Consider the effect of disconnecting edge \((u, v)\) (where \(u\) is the parent of \(v\)).
(A) When entering a vertex \(x\) on the IN side
Access from vertex \(x\) to the vertices on the OUT side, which would normally be reachable, is blocked by the disconnection of edge \((u, v)\). - The distance from \(x\) to \(v\) is \(dist[x][v]\). - Upon crossing the disconnected edge to reach \(u\), the remaining travel distance becomes \(rem = D - 1 - dist[x][v]\). - If \(rem \ge 0\), the vertices on the OUT side that are within distance \(rem\) from \(u\) (which would normally be reachable) become unreachable. - This “lost data amount” can be calculated as follows: $\(\text{Lost data} = S_{all}[u][rem] - S_{in}[v][rem - 1]\)\( (All vertices within distance \)rem\( from \)u\(, excluding those on the IN side that are within distance \)rem\( from \)u\( (which is equivalent to being within distance \)rem-1\( from \)v$)).
Therefore, the gained data amount is: $\(\text{Gained data} = S_{all\_D}[x] - (S_{all}[u][rem] - S_{in}[v][rem - 1])\)$
(B) When entering a vertex \(y\) on the OUT side
Access from vertex \(y\) to the vertices on the IN side is blocked. - The distance from \(y\) to \(u\) is \(dist[y][u]\). - Upon crossing the disconnected edge to reach \(v\), the remaining travel distance becomes \(rem = D - 1 - dist[y][u]\). - If \(rem \ge 0\), the vertices on the IN side that are within distance \(rem\) from \(v\) (which would normally be reachable) become unreachable. - By definition, this “lost data amount” is exactly \(S_{in}[v][rem]\).
Therefore, the gained data amount is: $\(\text{Gained data} = S_{all\_D}[y] - S_{in}[v][rem]\)$
4. Aggregation
For each edge \((u, v)\), we find the maximum of (A) over all vertices \(x\) on the IN side, denoted as \(M_{in}[v]\), and the maximum of (B) over all vertices \(y\) on the OUT side, denoted as \(M_{out}[v]\). The maximum data Takahashi can obtain when Aoki disconnects this edge is \(\max(M_{in}[v], M_{out}[v])\).
We compute this value for all edges, and the minimum of these values (and the maximum value when no edges are disconnected) will be the final answer.
Complexity
Time Complexity: \(O(N^2)\)
- All-pairs shortest paths calculation (BFS \(N\) times): \(O(N^2)\)
- Computing cumulative sums \(S_{all}, S_{in}\): \(O(N^2)\)
- For each edge \(v\), we perform \(O(1)\) calculations for the vertices on the IN side (\(sz[v]\) vertices) and the vertices on the OUT side (\(N - sz[v]\) vertices). This takes \(O(N)\) per edge, leading to \(O(N^2)\) in total.
- Thus, the overall time complexity is \(O(N^2)\), which is well within the time limit.
Space Complexity: \(O(N^2)\)
- We use \(O(N^2)\) memory to store the shortest path table
distand the cumulative sum tablesS_allandS_in. For \(N = 3000\), the number of elements in each table is approximately \(9 \times 10^6\), which easily fits within the memory limit (typically 1024MB).
Implementation Details
Subtree Check (Euler Tour Application): We can distinguish whether a vertex belongs to the subtree of \(v\) (IN side) or not (OUT side) efficiently by using the pre-order index \(L[v]\) and the subtree size \(sz[v]\). A vertex is on the IN side if and only if its index lies in the range \([L[v], L[v] + sz[v])\).
Index Boundary Conditions: We need to carefully handle edge cases, such as when the remaining distance \(rem\) is negative, or when cumulative sum indices go out of bounds (e.g., \(rem - 1 < 0\)). In the provided code, these are handled safely using conditional branches like
rem >= 0and ternary operators likerem > 0.Source Code
import sys
def solve():
input = sys.stdin.read
data = input().split()
if not data:
return
N = int(data[0])
D = int(data[1])
V = [int(x) for x in data[2 : N + 2]]
adj = [[] for _ in range(N)]
idx = N + 2
for _ in range(N - 1):
u = int(data[idx]) - 1
v = int(data[idx + 1]) - 1
adj[u].append(v)
adj[v].append(u)
idx += 2
# BFS to find parent and topological order
parent = [-1] * N
order = []
stack = [0]
visited = [False] * N
visited[0] = True
while stack:
u = stack.pop()
order.append(u)
for v in adj[u]:
if not visited[v]:
visited[v] = True
parent[v] = u
stack.append(v)
L = [0] * N
for i, u in enumerate(order):
L[u] = i
sz = [1] * N
for u in reversed(order):
p = parent[u]
if p != -1:
sz[p] += sz[u]
R = [L[u] + sz[u] for u in range(N)]
# All pairs shortest path
dist = [[-1] * N for _ in range(N)]
for start in range(N):
d = dist[start]
d[start] = 0
queue = [start]
head = 0
while head < len(queue):
u = queue[head]
head += 1
curr_d = d[u]
for v in adj[u]:
if d[v] == -1:
d[v] = curr_d + 1
queue.append(v)
# S_all[u][k]
S_all = [[0] * (N + 1) for _ in range(N)]
for u in range(N):
su = S_all[u]
du = dist[u]
for v in range(N):
su[du[v]] += V[v]
for k in range(1, N + 1):
su[k] += su[k - 1]
# Precompute S_all_D
S_all_D = [S_all[i][D] for i in range(N)]
# S_in[v][k]
S_in = [[0] * (N + 1) for _ in range(N)]
for v in range(N):
sv = S_in[v]
dv = dist[v]
l = L[v]
r = R[v]
for idx in range(l, r):
x = order[idx]
sv[dv[x]] += V[x]
for k in range(1, N + 1):
sv[k] += sv[k - 1]
M_in = [0] * N
M_out = [0] * N
for v in range(1, N):
u = parent[v]
dv = dist[v]
su = S_all[u]
sv = S_in[v]
# M_in[v]
m_in = 0
l = L[v]
r = R[v]
for idx in range(l, r):
x = order[idx]
rem = D - 1 - dv[x]
val = S_all_D[x]
if rem >= 0:
val -= su[rem] - (sv[rem - 1] if rem > 0 else 0)
if val > m_in:
m_in = val
M_in[v] = m_in
# M_out[v]
m_out = 0
du = dist[u]
for idx in range(0, l):
y = order[idx]
rem = D - 1 - du[y]
val = S_all_D[y]
if rem >= 0:
val -= sv[rem]
if val > m_out:
m_out = val
for idx in range(r, N):
y = order[idx]
rem = D - 1 - du[y]
val = S_all_D[y]
if rem >= 0:
val -= sv[rem]
if val > m_out:
m_out = val
M_out[v] = m_out
ans = max(S_all_D)
for v in range(1, N):
cand = M_in[v]
if M_out[v] > cand:
cand = M_out[v]
if cand < ans:
ans = cand
print(ans)
if __name__ == "__main__":
solve()
This editorial was generated by gemini-3.5-flash-high.
投稿日時:
最終更新: