「頂点 \(i\) には \(i\) の子孫であるような頂点の番号を書き込むことはできない」という \(N\) 個の条件を満たすような書き込み方の個数を求める問題です。

包除原理を利用することを考えます。 すると、\(2^{N}\) 個ある条件の部分集合それぞれについて、部分集合に含まれる条件全てに違反するような書き込み方の個数を求めればよいことがわかります。

条件に違反する場所のみを決め、その他の場所は最後にまとめて書き込むことを考えます。また、\(i\) を根とする部分木に \(j\) 箇所条件に違反するように書き込む方法の個数を \(\mathrm{dp}(i,j)\) とします。答えは \(\sum_{j=0}^{N} (-1)^{j}\mathrm{dp}(1,j) (N-j)!\) で表すことができます。

DPテーブルは \(O(N^{2})\) で求めることができ、十分高速です。