問題概要
$N$ 頂点 $M $ 辺からなる単純無向グラフ（連結とは限らない）が与えられる．はじめ，各頂点 $i$ には整数 $a_i$ が書かれている．ここで，次の操作を任意回行うことができる．
- 辺 $\{ u, v \}$ を選ぶ．その後，$a_u \leftarrow a_u - 1$ と $a_v \leftarrow a_v + 1$ をする*1
操作終了後，各頂点 $i$ に書かれている値を $b_i$ にすることはできるか？
制約
- $1 \leq N \leq 2 \times 10^5$
- $0 \leq M \leq \min \left( \frac { N \times ( N - 1 ) } 2, 2 \times 10^5 \right)$
- $-10^9 \leq a_i, b_i \leq 10^9$
解法
求められているのは可能か不可能かの判定だけで，それを達成する操作列を構成することや，あるいは操作列の長さを最小化することなどは求められていないことを意識しておきます．
状況をちょっと噛み砕くと，次のようになります．
- はじめ，各頂点には $a_i$ 個のトークンが置かれている*2
- 「操作」は，隣接する 2 点 $u, v$ について，$u$ にあるトークンを一つつまんで $v$ に移動させる操作に対応する
- 最終的に，各頂点にあるトークンの数が $b_i$ 個になれば OK
操作に着目すると，いくつかのことが言えます．まずは，
- ある一つのトークンに着目し，それを対象に繰り返し操作すると，連結成分内の任意の場所に移動できる
です．この操作を繰り返せば更に，
- ある一つの頂点から，任意個のトークンをそこから可達 (reachable) な別の頂点へ移動できる
ということも言えます．連結成分や可達という言葉を使いましたが，この操作は明らかに，
- 連結成分内にあるトークンの総数を保存する
ということもすぐに分かります．よって，ある連結成分 $S$ について，$S$ 内の $a$ の総和 $\sum_{ v \in S } a_v$ と $b$ の総和 $\sum_{ v \in S } b_v$ が等しくなければならないということが分かります．これで必要条件が分かりました．先程の操作に関する observation から，操作では（連結成分内で）トークンを自由に移動させられます．ということは，（和が一定な範囲で）自由な配置を作れるということなので，実は十分条件にもなっています．
よって，各連結成分について $a$ の和と $b$ の和を比較してすべて一致しているか否かを判定することで問題を解くことができます．
計算量については，連結成分の検出に素集合データ構造を使った以下の実装では，$O( ( N + M ) \alpha( N ))$ 時間となります．
コード
class DisjointSetForest; // DisjointSetForest( N ) // find( x ) // same( x, y ) // unite( x, y ) // groups() // groupSize( x ) int main() { IN( int, N, M ); VI A( N ), B( N ); cin >> A >> B; DisjointSetForest dsf( N ); REP( M ) { IN( int, u, v ); --u, --v; dsf.unite( u, v ); } VT< LL > sums( N ); REP( i, N ) { sums[ dsf.find( i ) ] += A[i]; sums[ dsf.find( i ) ] -= B[i]; } cout << ( find_if( ALL( sums ), []( const auto s ){ return s; } ) == end( sums ) ? "Yes" : "No" ) << endl; return 0; }
