以降では、\(p = P/100, \;q = 1-p\) とします。

突然ですが、以下のゲームを考えます：

2 人のプレイヤー Alice と Bob がそれぞれ整数 \(a, b\) を持っています。最初、\(a = b = 0\) です。また、最初の手番は Alice とします。各ターンでは、手番を握っているプレイヤーが以下の操作を行います。

• 確率 \(p\) で自分の持っている数に 1 を足す。手番は自分が握ったまま次のターンへ進む。

• 確率 \(1-p\) で相手の持っている数に 1 を足す。さらに、手番を相手に渡して次のターンへ進む。

このゲームにおいて、\(a = x\) となるのが \(b = y\) となるのより先になる確率を \(P(x,y)\) とします。すると、元の問題 (頂点を 0-indexed に置き換える) において \(D_v\) は以下のような確率変数として表せます：

\[ D_v = \begin{cases} N - v & (\text{w.p. } P(N-v,v ))\\ v & (\text{w.p. } 1 - P(N-v, v)) \end{cases}. \]

従って、答えは以下のように表すことができます：

\[ \mathbb{E}\left[\sum_{v=0}^{N-1}D_v \right] = 2 \sum_{v=0}^{N-1} v\times P(v, N-v) - N\sum_{v=0}^{N-1} P(v,N-v) + \sum_{v=0}^{N-1}(N-v). \]

上式の右辺第三項は簡単に計算できるので、第一項と第二項を計算できれば良いです。

\(Q(x,y)\) を、ゲーム開始時の手番を Bob にしたときに \(a = x\) となるのが \(b = y\) となるのより先になる確率とします。このとき、\(x,y\geq 1\) について以下の漸化式が成立します：

\[ P(x,y) = p\cdot P(x-1,y) + (1-p)\cdot Q(x,y-1) \]

\[ Q(x,y) = p\cdot Q(x,y-1) + (1-p)\cdot P(x-1, y). \]

漸化式のベースケースは \(P(0,y) = Q(0,y) = 1,\; P(x,0) = Q(x,0) = 0\) です。これによって、\(n\geq 1\) について

\[ f_0(n) = \sum_{i = 0}^{n-1} P(i, n-i) \]

\[ g_0(n) = \sum_{i = 0}^{n-1} Q(i, n-i) \]

\[ f_1(n) = \sum_{i = 0}^{n-1} i\times P(i, n-i) \]

\[ g_1(n) = \sum_{i = 0}^{n-1} i\times Q(i, n-i) \]

とすれば、以下の漸化式を導出できます：

\[ \begin{bmatrix} f_0(n+1)\\ g_0(n+1)\\ f_1(n+1)\\ g_1(n+1)\\ 1 \end{bmatrix} = \begin{bmatrix} p & q & 0 & 0 & p\\ q & p & 0 & 0 & q\\ p & 0 & p & q & 0\\ q & 0 & q & p & 0\\ 0 & 0 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} f_0(n)\\ g_0(n)\\ f_1(n)\\ g_1(n)\\ 1 \end{bmatrix}. \]

従って、\(n = 1\) から始めて行列累乗を適用することで \(O(\log N)\) 時間で \(f_0(N), f_1(N)\) が得られます。求める答えは

\[ 2\times f_1(N) - N\times f_0(N) + \frac{N(N+1)}{2} \]

です。