各 \(i\) に対し，以下の条件を満たす極大な区間 \([L_i,R_i]\) を考えます．

• \(L_i \leq i \leq R_i\)
• 各 \(j \in [L_i,R_i]\) に対し，頂点 \(A_i\) は \(B_j\) の先祖 (or \(A_i=B_j\)) である．

イメージとしては，\(A_i\) が動けそうな範囲が \([L_i,R_i]\) です． しかし実際にはこの中でも動けない場所があるので，それを考えていきます．

まず重要な性質として，\([L_i,R_i]\) の集合は laminar です． つまり，これらの区間は中途半端に交わることはなく，木構造(のようなもの)を作ります．

\(A_i\) の値が大きい順\(=[L_i,R_i]\) の小さい順に処理を行います． \(A_i\) が動けそうな範囲 \([L_i,R_i]\) の中で，実際に動ける範囲を計算します． このためには，すでに “固定されている” 場所を管理する必要があります． ここで，”固定されている” 場所は，以下のように定義されます．

• 区間 \([L_i,R_i]\) の（区間の木構造における）部分木に入る区間の個数が \(k\) だとする．もし \(R_i-L_i+1=k\) が成り立つと，これらの \(k\) 個の区間に対応する値が \([L_i,R_i]\) 内を埋め尽くすことになる． これよりあとに処理する値は \([L_i,R_i]\) 内に侵入することが許されなくなる． この時，\([L_i,R_i]\) 内の場所は”固定されている”と呼ぶことにする．

\([L_i,R_i]\) を処理する際は，この区間が固定されている場所を含まないように縮小する必要があります． 縮小したあとの区間を \([l,r]\) と表します． 実は，\(A_i\) は \([l,r]\) 内の好きな場所に移動できます． というのも，動けない箇所とは何かを考えると，上で定義した固定されている箇所そのものだからです．

\([l,r]\) の好きな場所に移動できると述べましたが，実際に選べるのは今まで処理した値が置かれていない場所です． 「今まで処理した値が置かれている場所」の個数は，置き方によらず一定です． よって，今考えている \(A_i\) を置ける場所の候補が何通りあるかが確定します． これをすべての \(A_i\) について考えれば，最終的に何通りの \(A\) が作れるかがわかります．ただし，\(A_i\) の値に重複がある場合には適切な係数で割る必要があることに注意してください．

以上の手順を実装すればこの問題は解けます． 一番ボトルネックになりやすい部分は，\(L_i,R_i\) を求めるところでしょう． これは例えば，二分探索と \(B\) に対する区間LCAクエリで処理できます． 区間LCAクエリは区間内の頂点の dfs-order の min/max を保持しておくと \(O(\log M+\log N)\) 時間で計算できます．

以上をまとめると，計算量は \(O(N+M\log M(\log M+\log N)))\) になります． なお，区間minクエリやLCAクエリを\(O(1)\)で処理するようにすれば計算量の\(\log\)を一つ削減できます．

回答例(C++)