\(C_N\) を \(O(1)\) で求めることができます。
実は、
\(C_N=\begin{cases} 0 \; (N=1)\\ -1 \; (N=2)\\ \frac{-N}{3} \; (3 \leq N) \end{cases}\)
が成り立ちます。
帰納法などにより証明することもできますが、他の証明方法を紹介します。

\(3 \leq N\) とします。
頂点 \(1,2,\dots,N\) を用意し、各連結成分 \(S\) には整数 \(B(S)\) が割り振られていて最初は \(B(\{i\})=A_i\) とし、以下の操作を \(N-1\) 回行うという問題に言い換えることにします。

• 相異なる連結成分 \(S,T\) を選び、その間に辺を張り、新しい連結成分 \(S \cup T\) に \(B(\{S\})-B(\{T\})\) を割り当てる。

\(c_ic_j\) について考えます。
頂点 \(i,j\) をそれぞれ含む \(2\) つの連結成分 \(S,T\) がマージされるタイミングについて考えます。
\(2 \leq |S|\) のとき、\(c_i\) が \(1\) である確率と \(-1\) である確率は等しいため、\(c_ic_j\) の期待値は \(0\) です。
\(2 \leq |T|\) のとき、同様に \(c_ic_j\) の期待値は \(0\) です。
\(|S|=|T|=1\) のとき、それ以降どのように操作を行っても \(c_i\) と \(c_j\) の符号は相異なるままのため、\(c_ic_j=-1\) です。
よって、サイズが \(1\) の連結成分同士をマージする回数の期待値の \(-1\) 倍が \(C_N\) に等しいことがわかります。

言い換えた問題について、さらに、以下の条件を考えます。

• 最初に頂点 \(1,2,\dots,N\) を無作為に一列に並べる。
• その後は一度も並べ替えを行わず、隣り合う連結成分をマージするのを \(N-1\) 回繰り返す。

このとき、各操作後の連結成分集合の確率分布や選ばれる操作の確率分布は変わらないため、この条件を追加しても \(C_N\) は変化しないことがわかります。
\(i=1,2,\dots,N-1\) について、頂点 \(i,i+1\) をそれぞれ含む \(2\) つの連結成分のマージが \(P_i\) 回目の操作で行われるとします。
このとき、\((P_1,P_2,\dots,P_{N-1})\) は長さ \(N-1\) の順列であり、長さ \(N-1\) のすべての順列が同じ確率で生じます。
\(\{i\}\) と \(\{j\}\) のマージが行われる条件と確率について考えます。
\(2 \leq i \leq N-2\) のとき、これは \(P_{i-1},P_{i+1}>P_{i}\) と同値で、その確率は \(\frac{1}{3}\) です。
\(i=1\) のとき、これは \(P_{2}>P_{1}\) と同値で、その確率は \(\frac{1}{2}\) です。 \(i=N-1\) のとき、これは \(P_{N-2}>P_{N-1}\) と同値で、その確率は \(\frac{1}{2}\) です。
これらを足し合わせることで、上記の式が成り立つことがわかります。