概要

本問題は、木構造の道路ネットワークにおいて、「パス上のすべての辺への一括加算（補強工事）」を \(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ステップに分けて効率化を図ります。

1. 補強工事の高速化（木のいもす法） \(Q\) 回の補強工事による耐久値の加算を、1次元配列のいもす法（累積和）を木構造に拡張した「木のいもす法」を用いてまとめて行います。これにより、すべての工事が終わった後の各道路の最終的な耐久値を \(O(N + Q \log N)\) で一括計算できます。
2. 最小値クエリの高速化（ダブリング） 最終的な耐久値が求まった道路ネットワークに対して、ダブリングテーブル（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\) であるため、メモリ制限に対しても十分に余裕があります。

---

実装のポイント

1. 親のインデックス制約の活用: 「葉から根への累積和の伝播」を行う際、通常は木上のDFSなどが必要ですが、本問題では \(P_i < i\) が保証されているため、単にインデックスを \(N\) から \(2\) までデクリメントするループで正しく葉から順に処理できます。これにより実装が非常にシンプルかつ高速になります。

2. 例外処理 (\(a_k = b_k\)): 質問で \(a_k = b_k\) が指定された場合は、経路上に道路が存在しないため、答えは \(0\) となります。クエリ処理の最初で if (u == v) return 0LL; と判定して早期リターンを行います。

3. 高速な入出力: 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 によって生成されました。