J - 道路ネットワークの整備 / Road Network Development 解説 by admin
gemini-3.5-flash-thinkingOverview
This problem involves a tree structure (road network) where you perform \(Q\) queries that update (add durability values to) all edges (roads) on the path between two cities, and then answer \(R\) queries that ask for the minimum value of edges on the path between two cities.
Analysis
Naive Approach and Its Limitations
For each query, one could use Depth-First Search (DFS) or Breadth-First Search (BFS) to find the shortest path between two points (which is unique since the structure is a tree), and then update or scan the edges on the path one by one. However, this approach takes \(O(N)\) time per query in the worst case. The overall time complexity becomes \(O((Q + R) N)\), and under the constraints (\(N, Q, R \le 5 \times 10^4\)), this requires approximately \(5 \times 10^9\) operations in the worst case, which will not fit within the time limit (TLE).
Approach for Speedup
If instead of a tree structure, we had “range addition” and “range minimum queries” on a “1-dimensional array,” we could efficiently process each operation in \(O(\log N)\) using a Lazy Segment Tree. If we can transform path updates and queries on a tree into range updates and queries on an array, we can apply this powerful data structure. The representative technique for achieving this is Heavy-Light Decomposition (HLD).
Algorithm
1. Storing Edge Information at Vertices
Since segment trees and HLD fundamentally operate on vertices, we need to map edge information onto vertices. In a tree structure, for every vertex \(i\) (\(2 \le i \le N\)) other than the root (city 1), there exists a unique parent \(P_i\). Therefore, we manage the information of “the road connecting city \(i\) and its parent \(P_i\)” as the value of the child city \(i\). This allows us to replace operations on edges with operations on vertices excluding the root (city 1).
2. Heavy-Light Decomposition (HLD)
HLD is a technique that decomposes the vertices of a tree into several “heavy paths” and rearranges all vertices of the tree into a single linear array. By applying HLD, the path between any two points \(u, v\) in the tree is divided into \(O(\log N)\) contiguous intervals on the array.
3. Lazy Segment Tree
We construct a lazy segment tree to manage the array rearranged into one dimension by HLD. This segment tree supports the following two queries: - Range addition: Add \(x\) to all elements in the specified range. - Range minimum query: Retrieve the minimum value of elements in the specified range.
4. Query Processing
- Reinforcement work (addition query): Decompose the path between cities \(u, v\) into \(O(\log N)\) intervals using HLD, and perform a \(+1\) range addition on each interval using the lazy segment tree.
- Question (minimum query): Similarly decompose the path between cities \(a, b\) into \(O(\log N)\) intervals using HLD, retrieve the minimum value for each interval using the lazy segment tree, and return the minimum among all of them as the answer.
Complexity
Time complexity: \(O(N + (Q + R) \log^2 N)\)
- Building the HLD (tree traversal and determining heavy children) takes \(O(N)\).
- Initializing the lazy segment tree takes \(O(N)\).
- For each update/query, the path decomposition by HLD yields at most \(O(\log N)\) intervals, and operating on the segment tree for each interval takes \(O(\log N)\), so the time per query is \(O(\log^2 N)\).
- Therefore, the overall time complexity is \(O(N + (Q + R) \log^2 N)\), which comfortably fits within the time limit.
Space complexity: \(O(N)\)
- The memory required to store the tree’s adjacency list, various management arrays for HLD (
head,pos,depth,sz, etc.), and the segment tree (size \(2 \times 2^{\lceil \log_2 (N-1) \rceil}\)) is \(O(N)\).
- The memory required to store the tree’s adjacency list, various management arrays for HLD (
Implementation Notes
Avoiding Recursion (Iterative DFS) In Python, recursive calls have significant overhead and are limited by the maximum recursion depth (Recursion Limit), so the DFS for building the HLD is implemented iteratively using an explicit stack (loop). This ensures fast and safe execution.
Iterative Segment Tree The lazy segment tree is also implemented without recursive functions, using bit operations on a 1-dimensional array (iterative lazy segment tree), which dramatically improves the constant factor of execution speed.
Boundary Handling at the LCA (Lowest Common Ancestor) When processing the path between two points \(u, v\) with HLD, the two points eventually reach the same heavy path (same
head). At this point, the shallower vertex (closer to the root), which is the LCA itself, does not correspond to an edge on the path and must be excluded from processing. In the code, whenuandvreach the same heavy path, the range frompos[v] + 1topos[u] + 1is used as the target for updates/queries, correctly excluding vertexvitself (pos[v]), which is the LCA.Corner Case Handling
When \(N=1\), no roads exist, so \(0\) is immediately output for all questions.
When \(a_k = b_k\) in a question, no roads exist on the path, so the answer is \(0\).
Source Code
import sys
def solve():
# 入力の高速読み込み
input_data = sys.stdin.read().split()
if not input_data:
return
N = int(input_data[0])
if N == 1:
# N=1 の場合は道路が存在しないため、すべての質問に対する答えは 0
# Q や R の入力を読み飛ばす必要がある
idx = 1
# Q の読み込み
Q = int(input_data[idx])
idx += 1 + 2 * Q
# R の読み込み
R = int(input_data[idx])
out = ['0'] * R
print('\n'.join(out))
return
P = [0] * (N + 1)
W = [0] * (N + 1)
idx = 1
for i in range(2, N + 1):
P[i] = int(input_data[idx])
W[i] = int(input_data[idx+1])
idx += 2
Q = int(input_data[idx])
idx += 1
updates = []
for _ in range(Q):
u = int(input_data[idx])
v = int(input_data[idx+1])
updates.append((u, v))
idx += 2
R = int(input_data[idx])
idx += 1
queries = []
for _ in range(R):
a = int(input_data[idx])
b = int(input_data[idx+1])
queries.append((a, b))
idx += 2
# 隣接リストの構築
adj = [[] for _ in range(N + 1)]
for i in range(2, N + 1):
adj[P[i]].append(i)
# 部分木サイズ計算
sz = [1] * (N + 1)
for i in range(N, 1, -1):
sz[P[i]] += sz[i]
# 重い子の決定
heavy = [0] * (N + 1)
for i in range(2, N + 1):
p = P[i]
if heavy[p] == 0 or sz[i] > sz[heavy[p]]:
heavy[p] = i
# 重い子を隣接リストの先頭に移動
for u in range(1, N + 1):
if heavy[u] != 0:
h = heavy[u]
adj[u].remove(h)
adj[u].insert(0, h)
# HLDの順序決定 (非再帰DFS)
pos = [0] * (N + 1)
pos[1] = -1 # 根の pos を -1 にして、pos[1] + 1 = 0 となるようにする
head = [0] * (N + 1)
depth = [0] * (N + 1)
for i in range(2, N + 1):
depth[i] = depth[P[i]] + 1
cur_pos = 0
stack = [(1, 1)]
while stack:
u, h = stack.pop()
head[u] = h
if u != 1:
pos[u] = cur_pos
cur_pos += 1
for v in reversed(adj[u]):
stack.append((v, h if v == heavy[u] else v))
# 遅延評価セグメント木（非再帰）の初期化
size = 1
while size < N - 1:
size *= 2
height = size.bit_length() - 1
INF = 10**18
tree = [INF] * (2 * size)
lazy = [0] * (2 * size)
for i in range(2, N + 1):
tree[size + pos[i]] = W[i]
for i in range(size - 1, 0, -1):
tree[i] = min(tree[2 * i], tree[2 * i + 1])
# セグメント木の更新関数
def update(l, r, x):
if l >= r: return
l += size
r += size
l0, r0 = l, r
for s in range(height, 0, -1):
if (l0 >> s) << s != l0:
i = l0 >> s
val = lazy[i]
if val != 0:
tree[2*i] += val; lazy[2*i] += val
tree[2*i+1] += val; lazy[2*i+1] += val
lazy[i] = 0
if (r0 >> s) << s != r0:
i = (r0 - 1) >> s
val = lazy[i]
if val != 0:
tree[2*i] += val; lazy[2*i] += val
tree[2*i+1] += val; lazy[2*i+1] += val
lazy[i] = 0
while l < r:
if l & 1:
tree[l] += x
if l < size: lazy[l] += x
l += 1
if r & 1:
r -= 1
tree[r] += x
if r < size: lazy[r] += x
l >>= 1
r >>= 1
l, r = l0, r0
for s in range(1, height + 1):
if (l >> s) << s != l:
i = l >> s
tree[i] = min(tree[2*i], tree[2*i+1]) + lazy[i]
if (r >> s) << s != r:
i = (r - 1) >> s
tree[i] = min(tree[2*i], tree[2*i+1]) + lazy[i]
# セグメント木のクエリ関数
def query(l, r):
if l >= r: return INF
l += size
r += size
l0, r0 = l, r
for s in range(height, 0, -1):
if (l0 >> s) << s != l0:
i = l0 >> s
val = lazy[i]
if val != 0:
tree[2*i] += val; lazy[2*i] += val
tree[2*i+1] += val; lazy[2*i+1] += val
lazy[i] = 0
if (r0 >> s) << s != r0:
i = (r0 - 1) >> s
val = lazy[i]
if val != 0:
tree[2*i] += val; lazy[2*i] += val
tree[2*i+1] += val; lazy[2*i+1] += val
lazy[i] = 0
res = INF
while l < r:
if l & 1:
if tree[l] < res: res = tree[l]
l += 1
if r & 1:
r -= 1
if tree[r] < res: res = tree[r]
l >>= 1
r >>= 1
return res
# HLD上での更新
def hld_update(u, v, x):
while head[u] != head[v]:
if depth[head[u]] < depth[head[v]]:
u, v = v, u
update(pos[head[u]], pos[u] + 1, x)
u = P[head[u]]
if depth[u] < depth[v]:
u, v = v, u
if u != v:
update(pos[v] + 1, pos[u] + 1, x)
# HLD上でのクエリ
def hld_query(u, v):
if u == v:
return 0
res = INF
while head[u] != head[v]:
if depth[head[u]] < depth[head[v]]:
u, v = v, u
val = query(pos[head[u]], pos[u] + 1)
if val < res: res = val
u = P[head[u]]
if depth[u] < depth[v]:
u, v = v, u
if u != v:
val = query(pos[v] + 1, pos[u] + 1)
if val < res: res = val
return res
# 更新の実行
for u, v in updates:
hld_update(u, v, 1)
# クエリの処理
out = []
for a, b in queries:
ans = hld_query(a, b)
out.append(str(ans))
print('\n'.join(out))
if __name__ == '__main__':
solve()
This editorial was generated by gemini-3.5-flash-thinking.
投稿日時:
最終更新: