まず，ある順列 \(P\) がよいか否かを簡単に判定する方法を考えます．

ある先祖と子孫 \(u<v\) が存在し，\(v,u\) の順で隣接する箇所がある場合，\(P\) は明らかによい順列ではありません． このような \((u,v)\) を改善ペアと呼ぶことにします．

ここで，改善ペアが存在しない場合，\(P\) はよい順列であることが示せます．

改善ペアが存在しない \(P\) に対して操作を複数回行った結果，元より辞書順で小さくなると仮定し，矛盾を導きます． 辞書順で最小化した結果を \(Q\) とおきます． \(P,Q\) が初めて異なる位置を \(i\) として，\(Q_i=P_j\) とおきます． 各 \(i \leq k < j\) について，\(P_k,P_j\) を swap する必要があります．

\(k=j-1\) に注目します．\(P_{j-1},P_j\) は swap 可能ですが，\(P\) に改善ペアが存在しないことから，\(P_{j-1}\) は \(P_j\) の先祖だとわかります． すると，各 \(i \leq k < j-1\) について，\(P_k,P_j\) は swap 可能ということになります． ここで，\(P_{j-1}\) を位置 \(i\) まで持ってくる操作を考えると，\(Q\) より小さい順列を得ることが可能になり，\(Q\) が辞書順最小であることに矛盾します．よって示されました．

以上の考察より，改善ペアの存在しない \(P\) すべてについて \(\operatorname{hash}(P)\) を求めればよいとわかりました．

改善ペアが存在しないという条件を包除原理を用いて処理します．

説明が簡単になるので，とりあえず，\(\operatorname{hash}(P)\) の総和ではなく \(P\) の個数を求める問題を解いてみましょう． これは木DPでできます． \(dp[v][k]=\) 頂点 \(v\) の部分木内で改善ペアを \(k\) 個指定する方法が何通りあるか，とすればよいです． ただしあとのことを考えて，改善ペアの個数 \(k\) ではなく，改善ペアによって結ばれたパスの個数 \(k\) をキーに持つことにします． パスが \(k\) 個の場合，それを最後に並べる方法は \(k!\) 通り存在することになります． この並べ方も最後に決めるのではなく，DP の途中で決めていくことにします． つまり，パス \(a\) 本の部分木と \(b\) 本の部分木をマージする際には，\({a+b \choose a}\) 通りの”混ぜ方”があることになります．

\(\operatorname{hash}(P)\) の場合も基本は同じです． \(\operatorname{hash}(P)\) の中身は，各要素に注目し，その前にある要素の個数だけ \(B\) 倍した重みをかける，という式です． 木DPを行うときは，注目する要素の前にあるパスの個数 \(a\) と後ろにあるパスの個数 \(b\) をキーにすれば良いです． その部分木内に注目する要素があるか否かで \(2\) 系列のDPテーブルが登場します．

各頂点 \(v\) に対して，その部分木サイズの \(2\) 乗オーダーのサイズのDPテーブルを持つ必要があります． マージの計算量は \(4\) 乗になります． このDPを素直に実装すると計算量は \(O(N^4)\) になります．\(O(N^5)\) にならないのは，\(O(N^3)\) っぽいDPが \(O(N^2)\) になる有名テク (どんな名前があったっけ…)と同じ理由です．

解答例(C++)