概要

この問題は、貯水池と水路をグラフとして捉え、水を行き来させることができるグループ（連結成分）ごとに水をできるだけ均等に分配したときの、全体の「最大水量」と「最小水量」の差を求める問題です。

考察

1. 連結成分ごとに独立に考える

水路で直接、または間接的につながっている貯水池の間では自由に水を移動できますが、水路でつながっていない貯水池の間では水を移動させることができません。 したがって、この問題は連結成分（グループ）ごとに独立に考えてよいことになります。

2. グループ内での最適な分配

あるグループ \(C\) について、貯水池の数を \(S_C\)、水量の総和を \(W_C\) とします。 このグループ内で、水量の最大値と最小値の差を最も小さくするには、水をできるだけ均等に分配するのが最適です。

水をできるだけ均等に分配したとき、各貯水池の水量は以下のようになります。 - \(W_C\) が \(S_C\) で割り切れる場合：すべての貯水池の水量が \(\frac{W_C}{S_C}\) になります。 - 割り切れない場合：水量が \(\lfloor \frac{W_C}{S_C} \rfloor\)（切り捨て）の貯水池と、\(\lceil \frac{W_C}{S_C} \rceil\)（切り上げ）の貯水池に分かれます。

したがって、グループ \(C\) において達成できる「最小の水量」は \(\lfloor \frac{W_C}{S_C} \rfloor\) であり、「最大の水量」は \(\lceil \frac{W_C}{S_C} \rceil\) となります。

3. 「水量 1 リットル以上」の制約について

問題文には「どの操作の直後においても、すべての貯水池の水量は \(1\) リットル以上でなければならない」という制約があります。 初期状態で各貯水池には \(1\) リットル以上の水があるため、グループ内の総水量 \(W_C\) は貯水池の数 \(S_C\) 以上（\(W_C \geq S_C\)）が保証されています。 よって、均等に分配したときの最小値 \(\lfloor \frac{W_C}{S_C} \rfloor\) は必ず \(1\) 以上となり、この制約に違反することなく最適な分配を達成できます。

4. 全体での最大値と最小値の差

すべてのグループは互いに独立しているため、全体の水量の最小値を最も大きく（下限を高く）しようとしても、各グループ \(C\) の最小値 \(\lfloor \frac{W_C}{S_C} \rfloor\) のうちの「最小値」より大きくすることはできません。 同様に、全体の最大値を最も小さく（上限を低く）しようとしても、各グループ \(C\) の最大値 \(\lceil \frac{W_C}{S_C} \rceil\) のうちの「最大値」より小さくすることはできません。

したがって、求める最小の差は、すべてのグループにわたる以下の値の差になります。 - 全体の最小値の下限 \(A\): すべてのグループにおける \(\lfloor \frac{W_C}{S_C} \rfloor\) の最小値 - 全体の最大値の上限 \(B\): すべてのグループにおける \(\lceil \frac{W_C}{S_C} \rceil\) の最大値

このとき、答えは \(B - A\) となります。

アルゴリズム

1. グループ分け (DSU / Union-Find) DSU（素集合データ構造）を用いて、水路でつながっている貯水池をマージし、連結成分にグループ分けします。
2. グループごとの集計 各貯水池の初期水量 \(P_i\) を用いて、各グループの「貯水池の総数 \(S_C\)」と「水量の総和 \(W_C\)」を計算します。
3. 限界値の計算 各グループについて \(\lfloor \frac{W_C}{S_C} \rfloor\) と \(\lceil \frac{W_C}{S_C} \rceil\) を計算し、全体の最小値の下限 \(A\) と最大値の上限 \(B\) を更新します。
4. 出力 \(B - A\) を出力します。

計算量

• 時間計算量: \(O(N + M \alpha(N))\) DSU を用いたグループ分けに \(O(N + M \alpha(N))\) かかります（\(\alpha\) はアッカーマン関数の逆関数で、実質的に定数とみなせます）。その後のグループごとの集計と最小値・最大値の探索は \(O(N)\) で行えるため、全体として非常に高速に動作します。
• 空間計算量: \(O(N)\) DSU の親を表す配列や、各グループのサイズ \(S_C\)、総和 \(W_C\) を記録する配列に \(O(N)\) のメモリを使用します。

実装のポイント

• 切り上げ除算の整数計算 C++ などの整数型において、正の整数 \(a, b\) に対する切り上げ除算 \(\lceil \frac{a}{b} \rceil\) は、浮動小数点数を使わずに (a + b - 1) / b と書くことで、誤差なく高速に計算できます。

• 型に注意 水量の総和 \(W_C\) は最大で \(N \times \max(P_i) = 2 \times 10^5 \times 10^9 = 2 \times 10^{14}\) に達するため、32bit整数型（int）ではオーバーフローします。必ず 64bit整数型（C++ では long long）を使用してください。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <atcoder/dsu>

using namespace std;
using namespace atcoder;

int main() {
    // 入出力の高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    if (!(cin >> N >> M)) return 0;

    vector<long long> P(N);
    for (int i = 0; i < N; ++i) {
        cin >> P[i];
    }

    dsu d(N);
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        d.merge(u, v);
    }

    vector<long long> sum_W(N, 0);
    vector<long long> size_S(N, 0);

    for (int i = 0; i < N; ++i) {
        int leader = d.leader(i);
        sum_W[leader] += P[i];
        size_S[leader]++;
    }

    long long A_limit = -1;
    long long B_limit = -1;
    bool first = true;

    for (int i = 0; i < N; ++i) {
        if (size_S[i] > 0) {
            long long W = sum_W[i];
            long long S = size_S[i];
            long long floor_val = W / S;
            long long ceil_val = (W + S - 1) / S;

            if (first) {
                A_limit = floor_val;
                B_limit = ceil_val;
                first = false;
            } else {
                A_limit = min(A_limit, floor_val);
                B_limit = max(B_limit, ceil_val);
            }
        }
    }

    cout << B_limit - A_limit << "\n";

    return 0;
}

---

この解説は gemini-3.5-flash-thinking によって生成されました。