J - 道路ネットワークの整備 / Road Network Development 解説 by admin
gemini-3.5-flash-thinking概要
本問題は、木構造の道路ネットワークにおいて、「パス上のすべての辺への一括加算（補強工事）」を \(Q\) 回行った後、「パス上の辺の最小値取得（質問）」に \(R\) 回答える問題です。
クエリの先頭ですべての加算（補強工事）が行われ、その後にすべての最小値取得（質問）が行われるという「静的な更新」の性質を利用し、木のいもす法とダブリング（LCA・RMQ）を組み合わせることで高速に処理します。
考察
素朴なアプローチとその限界
各補強工事において、都市 \(u\) から都市 \(v\) へのパスに含まれる道路を1本ずつ辿って耐久値を \(1\) ずつ増やしていくと、1回の工事に最悪で \(O(N)\) の時間がかかります。同様に、質問クエリでもパス上の道路を1本ずつ確認して最小値を求めると、1回の質問に \(O(N)\) の時間がかかります。 この場合、全体の計算量は \(O(Q N + R N)\) となり、最大で \((5 \times 10^4) \times (5 \times 10^4) \approx 2.5 \times 10^9\) 回の計算が必要となるため、実行時間制限に間に合いません（TLE）。
高速化へのアプローチ
この問題は、「すべての加算クエリが、最小値クエリよりも前に行われる」という重要な特徴があります。したがって、以下の2ステップに分けて効率化を図ります。
- 補強工事の高速化（木のいもす法） \(Q\) 回の補強工事による耐久値の加算を、1次元配列のいもす法（累積和）を木構造に拡張した「木のいもす法」を用いてまとめて行います。これにより、すべての工事が終わった後の各道路の最終的な耐久値を \(O(N + Q \log N)\) で一括計算できます。
- 最小値クエリの高速化（ダブリング） 最終的な耐久値が求まった道路ネットワークに対して、ダブリングテーブル（RMQ）を構築します。これにより、各質問に対して \(O(\log N)\) でパス上の最小値を求めることができます。
アルゴリズム
1. LCA（最近共通祖先）の準備
木のいもす法やパスの遡上のために、任意の2頂点の LCA（最近共通祖先）を高速に求めるダブリングテーブルを構築します。
- up[k][i] : 頂点 \(i\) から根（都市1）の方向に \(2^k\) 回遡ったときの祖先頂点
2. 木のいもす法による一括加算
都市 \(u\) と都市 \(v\) を結ぶパス上のすべての道路に \(1\) を加算する操作を考えます。 \(u\) と \(v\) の LCA を \(L\) とします。差分を記録する配列 \(D\)（初期値はすべて \(0\)）を用意し、各工事に対して以下のように値を更新します。 - \(D[u] \leftarrow D[u] + 1\) - \(D[v] \leftarrow D[v] + 1\) - \(D[L] \leftarrow D[L] - 2\)
すべての補強工事に対してこの記録を行った後、葉から根の方向へ累積和を計算します。 本問題の制約として \(P_i < i\)（親の番号は必ず自分より小さい）が保証されているため、トポロジカルソートや深さ優先探索（DFS）を行う必要はなく、\(i = N\) から \(2\) まで逆順にループを回すだけで、葉から根への伝播が \(O(N)\) で完了します。 - \(D[P_i] \leftarrow D[P_i] + D[i]\)
この操作の後、道路 \(i\)（頂点 \(i\) とその親 \(P_i\) を結ぶ道路）の最終的な耐久値 \(W'_i\) は、初期耐久値 \(W_i\) を用いて以下のように求まります。 - \(W'_i = W_i + D[i]\)
3. ダブリングを用いたパス最小値クエリ（RMQ）
最終的な耐久値 \(W'_i\) に基づき、パス上の最小値を求めるためのダブリングテーブルを構築します。
- min_edge[k][i] : 頂点 \(i\) から根の方向に \(2^k\) 本の道路を遡ったときの、それら道路の耐久値の最小値
このテーブルは、以下の遷移式によって \(O(N \log N)\) で構築できます。
- min_edge[k][i] = min(min_edge[k - 1][i], min_edge[k - 1][up[k - 1][i]])
各質問 \((a, b)\) に対しては、LCA を求める手順と同様に、深さが深い方の頂点を min_edge を参照しながら引き上げ、最終的に2つの頂点が出会うまでの経路上の最小値を集計します。1クエリあたり \(O(\log N)\) で処理可能です。
計算量
時間計算量: \(O((N + Q + R) \log N)\)
- LCA 用ダブリングテーブルの構築: \(O(N \log N)\)
- \(Q\) 回のいもす法（LCA取得含む）: \(O(Q \log N)\)
- 累積和の伝播と最終耐久値の計算: \(O(N)\)
- パス最小値用ダブリングテーブルの構築: \(O(N \log N)\)
- \(R\) 回の最小値クエリ: \(O(R \log N)\)
- 全体として、制約 \(N, Q, R \le 5 \times 10^4\) に対して十分高速に動作します（数ミリ秒〜数十ミリ秒程度）。
空間計算量: \(O(N \log N)\)
- ダブリングテーブル
upおよびmin_edgeの保持に \(O(N \log N)\) のメモリを使用します。\(N \le 5 \times 10^4, \log N \approx 17\) であるため、メモリ制限に対しても十分に余裕があります。
- ダブリングテーブル
実装のポイント
親のインデックス制約の活用: 「葉から根への累積和の伝播」を行う際、通常は木上のDFSなどが必要ですが、本問題では \(P_i < i\) が保証されているため、単にインデックスを \(N\) から \(2\) までデクリメントするループで正しく葉から順に処理できます。これにより実装が非常にシンプルかつ高速になります。
例外処理 (\(a_k = b_k\)): 質問で \(a_k = b_k\) が指定された場合は、経路上に道路が存在しないため、答えは \(0\) となります。クエリ処理の最初で
if (u == v) return 0LL;と判定して早期リターンを行います。高速な入出力: C++においては、入力されるデータ数が多いため、
ios_base::sync_with_stdio(false); cin.tie(NULL);を用いて入出力速度を向上させています。ソースコード
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const long long INF = 4e18;
int main() {
// 高速な入出力
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N;
if (!(cin >> N)) return 0;
vector<int> P(N + 1);
vector<long long> W(N + 1, 0);
for (int i = 2; i <= N; ++i) {
cin >> P[i] >> W[i];
}
// 各都市の深さを計算
vector<int> depth(N + 1, 0);
depth[1] = 0;
for (int i = 2; i <= N; ++i) {
depth[i] = depth[P[i]] + 1;
}
// ダブリングテーブルのサイズを決定
int logN = 0;
while ((1 << logN) <= N) logN++;
logN++;
// LCA用ダブリングテーブルの構築
vector<vector<int>> up(logN, vector<int>(N + 1, 1));
for (int i = 1; i <= N; ++i) {
up[0][i] = P[i];
}
up[0][1] = 1;
for (int k = 1; k < logN; ++k) {
for (int i = 1; i <= N; ++i) {
up[k][i] = up[k - 1][up[k - 1][i]];
}
}
// LCAを求める関数
auto get_lca = [&](int u, int v) {
if (depth[u] < depth[v]) swap(u, v);
for (int k = logN - 1; k >= 0; --k) {
if (depth[u] - (1 << k) >= depth[v]) {
u = up[k][u];
}
}
if (u == v) return u;
for (int k = logN - 1; k >= 0; --k) {
if (up[k][u] != up[k][v]) {
u = up[k][u];
v = up[k][v];
}
}
return up[0][u];
};
int Q;
if (!(cin >> Q)) return 0;
// 木のいもす法（差分更新）用の配列
vector<long long> D(N + 1, 0);
for (int j = 0; j < Q; ++j) {
int u, v;
cin >> u >> v;
int lca = get_lca(u, v);
D[u] += 1;
D[v] += 1;
D[lca] -= 2;
}
// 葉から根へ累積和を伝播させる
for (int i = N; i >= 2; --i) {
D[P[i]] += D[i];
}
// 補強工事後の各道路の耐久値を計算
vector<long long> W_prime(N + 1, 0);
for (int i = 2; i <= N; ++i) {
W_prime[i] = W[i] + D[i];
}
// パス最小値クエリ用ダブリングテーブルの構築
vector<vector<long long>> min_edge(logN, vector<long long>(N + 1, INF));
for (int i = 2; i <= N; ++i) {
min_edge[0][i] = W_prime[i];
}
min_edge[0][1] = INF;
for (int k = 1; k < logN; ++k) {
for (int i = 1; i <= N; ++i) {
min_edge[k][i] = min(min_edge[k - 1][i], min_edge[k - 1][up[k - 1][i]]);
}
}
// パス上の最小耐久値を求める関数
auto query_min = [&](int u, int v) {
if (u == v) return 0LL;
long long ans = INF;
if (depth[u] < depth[v]) swap(u, v);
for (int k = logN - 1; k >= 0; --k) {
if (depth[u] - (1 << k) >= depth[v]) {
ans = min(ans, min_edge[k][u]);
u = up[k][u];
}
}
if (u == v) return ans;
for (int k = logN - 1; k >= 0; --k) {
if (up[k][u] != up[k][v]) {
ans = min({ans, min_edge[k][u], min_edge[k][v]});
u = up[k][u];
v = up[k][v];
}
}
ans = min({ans, min_edge[0][u], min_edge[0][v]});
return ans;
};
int R;
if (!(cin >> R)) return 0;
for (int k = 0; k < R; ++k) {
int a, b;
cin >> a >> b;
cout << query_min(a, b) << "\n";
}
return 0;
}
この解説は gemini-3.5-flash-thinking によって生成されました。
投稿日時:
最終更新: