九州大学プログラミングコンテスト2018 E - Treeone

解法

まず、 $A_{i}$ を変える、としたとき、どんな数字に変えればよいか、ということを考えてみます。
このとき、部分列の総和に影響がでるのは、もちろん $A_{i}$ を部分列に含むものについてのみで、含まないものは総和が変化することはありません。
さて、もともと $A_{i}$ を部分列に含み、かつ総和が0であったものについては、必ず総和が0ではなくなるので、その分たぴさが減少します。
逆に、総和が0でなかった場合、 $A_{i}$ の数字の変更によって、総和が0になってしまうパターンが存在します。
現在の総和が $X$ で合った場合、 $A_{i}$ を、 $A_{i} - X$ にしてしまうと、その部分列は総和が0になり、たぴさが上昇します。逆に、この値以外であれば、たぴさが上昇することはありません。
全ての部分列について、このような”変更後に総和が0になってしまう値”が存在しますが、逆にそれらとは違う、別の値に変更することによって、確実にたぴさの上昇を抑えることができます。
結果として、 $A_{i}$ を変更する、と決めたときのたぴさの最小値は、

$A_{i}$ を含まない部分列のうち、総和が0になるものの個数

となります。あとはこれを計算することができれば、答えを求めることができます。
$A_{i}$ を含まないものについて考えるので、まず区間を $[1,i),(i,N]$ に分割することができます。
$[1,i)$ で総和が0になる部分列の個数を求めることについて考えます。
$\displaystyle S[i][j] = \sum_{k=i}^{j}A_{k}$
とします。
$S[i][j] = 0$
になるには、 $S[1][i-1] = S[1][j]$ となる必要があります。
つまり、部分列の右端が $j$ になるような、部分列の総和が0になる区間の個数は、 $S[1][i-1] = S[1][j]$ となるような $i$ の個数、となります。
ということで、 $S[1][i] = X$ となるような $i$ の個数を、 $X$ をキーとするmapか何かに格納しておくことで、累積和を計算しつつ、mapの更新を行い、区間の右端が $i$ となるような、総和が0となる部分列の個数を求めることができます。
$[1,i)$ で総和が0になる部分列の個数は、部分列の右端が $j$ になるような、部分列の総和が0になる区間の個数の累積和を $i$ までとることで求めることができます。
そして、 $(i,N]$ については、数列をさかさまにして、同様の操作を行うことで求めることができます。ので、あとは、変更する数字の場所を全探索して、それぞれにおけるたぴさの最小値を計算していけば、その中で最も値が小さかったものが答えになります。