木の場合の解法

各辺 \(e\) について、辺 \(e\) を切ってできる \(2\) つの木の片方（どちらでもよい）を \(X_e\) とおきます。また、\(S_e := |\sum_{v \in X_e} A_v - \sum_{v \in X_e} B_v|\) とおきます。このとき、問題の答えは \(\sum_{e} S_e\) となります。これは

• 任意の操作で \(\sum_{e} S_e\) が高々 \(1\) しか減らないこと
• 必ず \(1\) 減らす操作が存在すること

の \(2\) つから示すことができます。

元問題の解法

操作によってある頂点に存在する駒の個数が負になることも許すことにします。これを許しても、適切に操作の順番を入れ替えることで不正でない操作列に変換可能であることを最後に証明します。

\(N\) 頂点 \(N\) 辺の単純無向連結グラフはサイクルをただ一つ持ちます。この唯一のサイクルを \(C\) とおきます。一般性を失わず、\(C\) 上の頂点が順に \(1, 2, \ldots, k\) であるとします。

まず、\(C\) に属さない頂点の駒の需給をすべて満たしておきます。これは \(C\) の辺をすべて削除し、各連結成分において \(C\) に属する唯一の頂点を根とした根付き木を考え、葉から順に需給を満たすように操作を行っていけばよいです。このときの操作回数は木の場合と同様に計算できます。

この操作の結果、\(i\in C\) には駒が \(a_i\) 個あるとします。あとは、\(C\) 上の駒の需給を最小回数で満たせばよいです。

\(i = 1, 2, \ldots, k\) に対し、頂点 \(i\) から頂点 \(i+1\) に渡す駒の数を \(c_i\) と置きます。ただし頂点 \(k+1\) は頂点 \(1\) とみなします。また、\(c_i < 0\) である場合は、\(-c_i\) だけ頂点 \(i+1\) から頂点 \(i\) に駒を渡すとみなします。すると、\(C\) 上の最小の操作回数は \(\sum_i |c_i|\) として考えられる最小値と等しいです。

ここで \(c_1\) を任意に固定してみます。すると \(a_2 + c_1 - c_2 = B_2\) より、\(c_2\) が一意に定まります。すると \(a_3 + c_2 - c_3 = B_3\) より、\(c_3\) が一意に定まります。これを続けていくと、\(c_2, c_3, \ldots, c_k\) がすべて一意に定まります。これらの情報から \(c_1\) をいくつにすれば答えを最小化できるかが定まり、答えが求まります。

このことから、最適解のうちサイクル上のある \(1\) 辺を使わないようなものが存在することが証明できます。したがって、その辺をはじめから無かったものとみなし、木の場合の操作を行えば不正な操作は起こりません。

実装においては、\(c_1 = 0\) と固定して他の \(c_i\) をすべて求めてから、\(c_i\) たちの中央値を \(0\) にするように \(c\) 全体に定数を加算すると楽です。

計算量は \(\mathrm{O}(N)\) や \(\mathrm{O}(N\log N)\) になります。