J - 道路ネットワークの整備 / Road Network Development 解説 by admin
gemini-3.5-flash-thinkingOverview
This problem involves a tree-structured road network where “bulk addition to all edges on a path (reinforcement work)” is performed \(Q\) times, followed by answering \(R\) “minimum value queries on edges along a path (questions)”.
By leveraging the “static update” property where all additions (reinforcement work) are performed first, followed by all minimum value queries (questions), we can efficiently process everything by combining tree difference arrays (imos method on trees) with doubling (LCA & RMQ).
Analysis
Naive Approach and Its Limitations
For each reinforcement work, if we traverse each road on the path from city \(u\) to city \(v\) one by one and increment the durability by \(1\), a single operation takes \(O(N)\) time in the worst case. Similarly, for query operations, if we check each road on the path one by one to find the minimum, a single query takes \(O(N)\) time. In this case, the total computation is \(O(Q N + R N)\), which requires up to \((5 \times 10^4) \times (5 \times 10^4) \approx 2.5 \times 10^9\) operations, exceeding the time limit (TLE).
Approach for Optimization
This problem has the important property that “all addition queries are performed before any minimum value queries.” Therefore, we divide the solution into the following two steps for efficiency:
- Speeding up reinforcement work (tree imos method) We batch-process the durability additions from \(Q\) reinforcement operations using the “tree imos method,” which extends the one-dimensional imos method (prefix sums) to tree structures. This allows us to compute the final durability of each road after all operations in \(O(N + Q \log N)\).
- Speeding up minimum value queries (doubling) We build a doubling table (RMQ) on the road network with the computed final durability values. This allows us to answer each query for the minimum value on a path in \(O(\log N)\).
Algorithm
1. LCA (Lowest Common Ancestor) Preparation
We build a doubling table for efficiently computing the LCA of any two vertices, which is needed for the tree imos method and path traversal.
- up[k][i]: The ancestor vertex reached by going \(2^k\) steps toward the root (city 1) from vertex \(i\)
2. Bulk Addition Using the Tree Imos Method
Consider the operation of adding \(1\) to all roads on the path connecting city \(u\) and city \(v\). Let \(L\) be the LCA of \(u\) and \(v\). We prepare a difference array \(D\) (initialized to all \(0\)s) and update values for each operation as follows: - \(D[u] \leftarrow D[u] + 1\) - \(D[v] \leftarrow D[v] + 1\) - \(D[L] \leftarrow D[L] - 2\)
After recording this for all reinforcement operations, we compute the prefix sum from leaves toward the root. Since the constraint \(P_i < i\) (a parent’s index is always smaller than the child’s) is guaranteed in this problem, there is no need for topological sorting or depth-first search (DFS). Simply iterating in reverse from \(i = N\) down to \(2\) completes the leaf-to-root propagation in \(O(N)\). - \(D[P_i] \leftarrow D[P_i] + D[i]\)
After this operation, the final durability \(W'_i\) of road \(i\) (the road connecting vertex \(i\) and its parent \(P_i\)) is computed using the initial durability \(W_i\) as follows: - \(W'_i = W_i + D[i]\)
3. Path Minimum Query (RMQ) Using Doubling
Based on the final durability values \(W'_i\), we build a doubling table for finding the minimum value on a path.
- min_edge[k][i]: The minimum durability among the \(2^k\) roads traversed when going from vertex \(i\) toward the root
This table can be constructed in \(O(N \log N)\) using the following recurrence:
- min_edge[k][i] = min(min_edge[k - 1][i], min_edge[k - 1][up[k - 1][i]])
For each query \((a, b)\), similar to the LCA computation procedure, we lift the deeper vertex while referencing min_edge, and aggregate the minimum value along the path until the two vertices meet. Each query can be processed in \(O(\log N)\).
Complexity
Time Complexity: \(O((N + Q + R) \log N)\)
- Building the LCA doubling table: \(O(N \log N)\)
- \(Q\) imos operations (including LCA computation): \(O(Q \log N)\)
- Prefix sum propagation and final durability computation: \(O(N)\)
- Building the path minimum doubling table: \(O(N \log N)\)
- \(R\) minimum value queries: \(O(R \log N)\)
- Overall, this runs sufficiently fast for the constraints \(N, Q, R \le 5 \times 10^4\) (on the order of a few milliseconds to tens of milliseconds).
Space Complexity: \(O(N \log N)\)
- The doubling tables
upandmin_edgeuse \(O(N \log N)\) memory. Since \(N \le 5 \times 10^4, \log N \approx 17\), there is ample room within the memory limit.
- The doubling tables
Implementation Notes
Leveraging the parent index constraint: When performing “prefix sum propagation from leaves to root,” a DFS on the tree is normally required. However, since \(P_i < i\) is guaranteed in this problem, we can correctly process nodes in leaf-to-root order by simply decrementing the index from \(N\) to \(2\) in a loop. This makes the implementation very simple and fast.
Edge case handling (\(a_k = b_k\)): When a query specifies \(a_k = b_k\), there are no roads on the path, so the answer is \(0\). We handle this with an early return at the beginning of query processing:
if (u == v) return 0LL;.Fast I/O: In C++, since the amount of input data is large, we use
ios_base::sync_with_stdio(false); cin.tie(NULL);to improve I/O speed.Source Code
#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;
}
This editorial was generated by gemini-3.5-flash-thinking.
投稿日時:
最終更新: