\(i\) 回目の行動後に高橋君が頂点 \(j\) にいて，かつ高橋君のレベルが \(k\) であるような確率を \(p(i,j,k)\) と置きます．また，\(\mathrm{dp}0,\mathrm{dp}1,\mathrm{dp}2\) を次で定義します：

• \(\mathrm{dp}0[i][j]\)：\(\displaystyle\sum_{k=0}^K k^0\cdot p(i,j,k)\) （ただし \(0^0=1\) とします）
• \(\mathrm{dp}1[i][j]\)：\(\displaystyle\sum_{k=0}^K k^1\cdot p(i,j,k)\)
• \(\mathrm{dp}2[i][j]\)：\(\displaystyle\sum_{k=0}^K k^2\cdot p(i,j,k)\)

このとき，\(i\) 回目の行動で頂点 \(u\) から頂点 \(v\) に移動するときの遷移は，頂点 \(u\) の次数を \(S\) として次のようになります．

• \(p(i,v,k)\ +=\dfrac{p(i-1,u,k)}{S}\)
• \(\mathrm{dp}0[i][v]\ +=\displaystyle\sum_{k=0}^K k^0\cdot\dfrac{p(i-1,u,k)}{S}\left(=\dfrac{\mathrm{dp}0[i-1][u]}{S}\right)\)
• \(\mathrm{dp}1[i][v]\ +=\displaystyle\sum_{k=0}^K k^1\cdot\dfrac{p(i-1,u,k)}{S}\left(=\dfrac{\mathrm{dp}1[i-1][u]}{S}\right)\)
• \(\mathrm{dp}2[i][v]\ +=\displaystyle\sum_{k=0}^K k^2\cdot\dfrac{p(i-1,u,k)}{S}\left(=\dfrac{\mathrm{dp}2[i-1][u]}{S}\right)\)

Python のコードだと以下のようになります（実際には，除算は \(\mathrm{mod} 998244353\) 上で行う必要があります）：

for v in range(n):
  s=len(edge[v]) # s は頂点 v の次数
  for u in edge[v]: # 頂点 v と結ばれている頂点を走査する
    dp0[i][u]+=dp0[i-1][v]/s
    dp1[i][u]+=dp1[i-1][v]/s
    dp2[i][u]+=dp2[i-1][v]/s

\(i\) 回目の行動におけるイベントについては，各頂点 \(v\) に対して以下のように処理をします．

• $C_v=1$ のとき：答えに $\mathrm{dp}2[i][v]$ を加える．
• $C_v=0$ のとき：$p(i,v,k),\mathrm{dp}0[i][v],\mathrm{dp}1[i][v],\mathrm{dp}2[i][v]$ は次のように変化させる．
  • $p(i,v,k)\leftarrow p(i,v,k-1)$
  • $\mathrm{dp}0[i][v]\leftarrow \displaystyle\sum_{k=1}^K k^0\cdot p(i,v,k-1)=\mathrm{dp}0[i][v]$ （変化しない）
  • $\mathrm{dp}1[i][v]\leftarrow \displaystyle\sum_{k=1}^K k^1\cdot p(i,v,k-1)=\sum_{k=0}^K (1+k)\cdot p(i,v,k)=\mathrm{dp}0[i][v]+\mathrm{dp}1[i][v]$
  • $\mathrm{dp}2[i][v]\leftarrow \displaystyle\sum_{k=1}^K k^2\cdot p(i,v,k-1)=\sum_{k=0}^K (1+2k+k^2)\cdot p(i,v,k)=\mathrm{dp}0[i][v]+2\mathrm{dp}1[i][v]+\mathrm{dp}2[i][v]$

Python のコードだと以下のようになります：

for v in range(n):
  if c[v]==0:
    dp1[i][v],dp2[i][v]=dp0[i][v]+dp1[i][v],dp0[i][v]+2*dp1[i][v]+dp2[i][v]
  else:
    ans+=dp2[i][v]

以上のような遷移を行えばよいです．計算量は \(O(K(N+M))\) になります．

実装例 (pypy)