J - 道路ネットワークの整備 / Road Network Development 解説 by admin
gemini-3.5-flash-thinking概要
本問題は、木構造（道路ネットワーク）において、2都市間のパス上にあるすべての辺（道路）の値を更新（耐久値の加算）するクエリを \(Q\) 回行い、その後、2都市間のパス上にある辺の最小値を求めるクエリに \(R\) 回答える問題です。
考察
素朴なアプローチとその限界
各クエリごとに、深さ優先探索（DFS）や幅優先探索（BFS）を用いて2点間の最短パス（木構造であるため一意に定まります）を求め、パス上の辺を1つずつ更新・走査する方法が考えられます。 しかし、この方法では1クエリあたり最悪 \(O(N)\) の時間がかかります。全体での計算量は \(O((Q + R) N)\) となり、制約（\(N, Q, R \le 5 \times 10^4\)）のもとでは、最悪で \(5 \times 10^9\) 回程度の演算が必要になり、実行時間制限に間に合いません（TLE）。
高速化へのアプローチ
もし、木構造ではなく「1次元の配列」に対する「区間加算」と「区間最小値取得」であれば、遅延評価セグメント木（Lazy Segment Tree）を用いることで、1回あたり \(O(\log N)\) で高速に処理できます。 木構造に対するパスの更新や取得を、配列に対する区間の更新や取得に変換できれば、この強力なデータ構造を適用できます。これを行うための代表的な手法が重軽分解（Heavy-Light Decomposition, HLD）です。
アルゴリズム
1. 辺の情報を頂点に持たせる
セグメント木やHLDは基本的に頂点に対して機能するため、辺の情報を頂点に載せる必要があります。 木構造では、根（都市1）以外のすべての頂点 \(i\)（\(2 \le i \le N\)）に対して、一意な親 \(P_i\) が存在します。そこで、「都市 \(i\) とその親 \(P_i\) を結ぶ道路」の情報を、子である都市 \(i\) の値として管理します。 これにより、辺に対する操作を、根（都市1）を除く頂点に対する操作に置き換えることができます。
2. 重軽分解（HLD）
HLDは、木の頂点をいくつかの「ヘビーパス（重いパス）」に分解し、木全体の頂点を1列の配列に並べ替える手法です。 HLDを適用することで、木における任意の2点 \(u, v\) 間のパスは、配列上での \(O(\log N)\) 個の連続する区間に分割されます。
3. 遅延評価セグメント木
HLDによって1次元に並べ替えられた配列を管理する遅延評価セグメント木を構築します。このセグメント木は以下の2つのクエリをサポートします。 - 区間加算: 指定された区間の要素すべてに \(x\) を加える。 - 区間最小値取得: 指定された区間の要素の最小値を取得する。
4. クエリの処理
- 補強工事（加算クエリ）: 都市 \(u, v\) 間のパスをHLDによって \(O(\log N)\) 個の区間に分解し、それぞれの区間に対して遅延評価セグメント木を用いて \(+1\) の区間加算を行います。
- 質問（最小値クエリ）: 都市 \(a, b\) 間のパスを同様に \(O(\log N)\) 個の区間に分解し、それぞれの区間に対して遅延評価セグメント木を用いて最小値を取得し、それらのうちの最小値を回答とします。
計算量
時間計算量: \(O(N + (Q + R) \log^2 N)\)
- HLDの構築（木の走査と重い子の決定）に \(O(N)\) かかります。
- 遅延評価セグメント木の初期化に \(O(N)\) かかります。
- 各更新・質問クエリにおいて、HLDによるパスの分解で最大 \(O(\log N)\) 個の区間が得られ、それぞれの区間に対してセグメント木を \(O(\log N)\) で操作するため、1クエリあたりの計算量は \(O(\log^2 N)\) です。
- したがって、全体の時間計算量は \(O(N + (Q + R) \log^2 N)\) となり、実行時間制限に余裕で間に合います。
空間計算量: \(O(N)\)
- 木の隣接リスト、HLD用の各種管理配列（
head,pos,depth,szなど）、およびセグメント木（サイズ \(2 \times 2^{\lceil \log_2 (N-1) \rceil}\)）を保持するために必要なメモリは \(O(N)\) です。
- 木の隣接リスト、HLD用の各種管理配列（
実装のポイント
再帰の回避（非再帰DFS） Pythonでは再帰呼び出しのオーバーヘッドが大きく、最大再帰深度（Recursion Limit）の制限もあるため、HLDを構築するためのDFSはスタックを用いた非再帰（ループ）で実装しています。これにより、高速かつ安全に動作します。
非再帰セグメント木 遅延評価セグメント木も、再帰関数を使わずに1次元配列のビット演算を用いて実装（非再帰遅延セグ木）することで、定数倍の実行速度を劇的に高速化しています。
LCA（最小共通祖先）での境界の扱い 2点 \(u, v\) のパスをHLDで処理する際、最終的に2点が同じヘビーパス（同じ
head）に到達します。このとき、より浅い（根に近い）方の頂点（LCA）自身は、パス上の辺に対応しないため、処理対象から除外する必要があります。 コード中では、uとvが同じヘビーパスに達した際、pos[v] + 1からpos[u] + 1までの範囲を更新・取得の対象とすることで、LCAであるv自身（pos[v]）を正しく除外しています。コーナーケースの処理
\(N=1\) の場合は道路が存在しないため、すべての質問に対して即座に \(0\) を出力します。
質問で \(a_k = b_k\) の場合は、経路上に道路が存在しないため、答えは \(0\) とします。
ソースコード
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()
この解説は gemini-3.5-flash-thinking によって生成されました。
投稿日時:
最終更新: