ある頂点 \(u\) が神童になる順列の個数を考える.
これは \(\{1, 2, \dots, N \}\) から \(u\) を含む \(u\) の先祖の数だけ数を選び出し, そのうち最大のものを \(u\) に割り当てて他の数を並べればいいので,
\[\combi{N}{d_u+1} \cdot d_u! \cdot (N-d_u-1)!\]
となる. ここで \(d_u\) は \(u\) の深さである.
これをすべての頂点について求めて合計すればいい. 階乗をあらかじめ計算しておけば \(O(N)\) で求められる.