E - Directed Tree Editorial by evima

The problem asks to count the ways to write numbers in the vertices satisfying the \(N\) conditions in the form: “Vertex \(i\) cannot have an index of a vertex that is a descendant of \(i\).”

Let us use the inclusion-exclusion principle. Then, for each of the \(2^{N}\) subsets of conditions, we want to find the number of ways that violate all conditions in that subset.

Let us just decide the positions violating the conditions and fill the other positions all at once in the end. Also, let \(\mathrm{dp}(i,j)\) be the number of ways to write numbers in the subtree rooted at \(i\) so that \(j\) positions are violating the conditions. Then, the answer can be represented as \(\sum_{j=0}^{N} (-1)^{j}\mathrm{dp}(1,j) (N-j)!\).

We can compute this DP table in \(O(N^{2})\) time, which is fast enough.

last update: