xuanxuan001 大神的題解寫得不是很清晰，所以這里是一篇人話題解。

先手玩一下。隨便寫一個排列與一棵合法樹：

很容易猜到，樹是合法的，當且僅當：它的任意子樹對應排列的標號是連續的。證明比較顯然，必要性由題意易知，充分性只需要從下往上遞歸構造樹即可。\(\square\)

這個說法并不嚴謹，因為這是一個環，可能出現連續段跨越環的情況。直接斷環成鏈比較麻煩，但是發現對 \(P\) 進行一些整體加減對答案并沒有影響，且排列相互之間沒影響，所以可以調整 \(P_{i,1}=1\)，并欽定 \(1\) 為根。

那么可以直接預處理出，每個區間 \([l,r]\) 是否可能構成子樹，即是否在 \(m\) 個排列中的標號都連續。（為了方便，注意到對所有排列整體做置換也不影響答案，所以可以調整出 \(P_{1,i}=i\)，這樣標號就是連續的了）

然后直接區間 DP 就行。具體設 \(f_{l,r}\) 表示標號 \([l,r]\) 中的數構成的樹個數，設其中根為 \(rt\)，其有若干個兒子 \(v_1,v_2,\cdots,v_k\)，就能把區間拆成 \([l,v_1)[v_1,v_2)\cdots[v_t,rt),\{rt\},(rt,v_{t+1})[v_{t+1},v_{t+2})\cdots[v_k,r]\)。于是增設 \(g_{l,r}\) 表示去除根后構成的樹的個數，那么 \(f_{l,r}=g_{l,rt-1}g_{rt+1,r}\)；\(g\) 再不斷由 \(g,f\) 合并即可。簡單來說就是模擬上面的區間拆分。

code，時間復雜度 \(O(n^2(n+m))\)。

回顧整道題，確實沒啥難度，每一步都有很強的引導性，包沒有 AT *3000 的......