\(i - P_i\) に辺を張ったグラフを考えると森になっています。簡単のため列の先頭に無限大を付け足すと木とみなせます。

このとき、頂点\(1,2,\cdots, N\) が行きがけ順に並んでいます。つまり、\(0\) を根として根付き木として考えたとき、各部分木はある \(l,r\) に対して区間 \([l, r]\) に対応していて、部分木の根が \(l\) となっています。

\(P\) を数える前に、木の形を固定したときに、グラフがその木に一致するような \(H\) の組が存在するかを考えてみましょう。これは、木の形に合うように貪欲に小さい値を割り当てていくことで判定できます。

詳細な条件としては、頂点 \(v\) の子が \(u_1 < u_2 \cdots < u_k\) のとき、辺の張られ方より \(H_v > \max(H_{u_1}, H_{u_2}, \cdots H_{u_k})\) かつ \( H_{u_1} \leq H_{u_2} \leq \cdots \leq H_{u_k}\) をみたす必要があり、これが全ての頂点の周りで成り立てばよいです。

よって、木を左の子から潜るようなDFSで順に貪欲に値を決めていき、各頂点ではmax(左の兄弟、子のmax + 1) を書くようにすると、全ての頂点について書かれうる最小の値が求まります。(この最小値は同時に達成できるということです)

この貪欲後の状態をキーとしたDPを考えます。

\(dp_木(l,r,x) := \)区間 \([l,r]\) だけ考えて上述の貪欲の結果根に \(x\) と書いてある木の個数

\(dp_森(l,r,x) :=\) 区間 \([l,r]\) のみを考慮して \(1\) 個以上木が並んでおり、貪欲の結果一番右の木の根に \(x\) が書いてあるような状態の個数

とすると、 \(dp_木\) は \(dp_森(l+1,r,x-1)\)

\(dp_森\) は \(dp_木 + \sum_{m=l}^{r-1} dp_森(l,m,a) * dp_木(m+1, r, b)\) (\(\max(a,b)=x)\) から求まるので累積和で高速化できます。(右につける木は別に考えておいた後、左の値より小さい場合に根だけ合わせるイメージです)

以上の時間計算量は \(O(N^4)\) となります。