Tree Coloring
Contest: Educational Codeforces Round 118 (Rated for Div. 2)
Difficulty rating: 2600
Tags: combinatorics, divide and conquer, fft

You are given a rooted tree consisting of $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$. The root of the tree is the vertex $$$1$$$.

You have to color all vertices of the tree into $$$n$$$ colors (also numbered from $$$1$$$ to $$$n$$$) so that there is exactly one vertex for each color. Let $$$c_i$$$ be the color of vertex $$$i$$$, and $$$p_i$$$ be the parent of vertex $$$i$$$ in the rooted tree. The coloring is considered beautiful if there is no vertex $$$k$$$ ($$$k > 1$$$) such that $$$c_k = c_{p_k} - 1$$$, i. e. no vertex such that its color is less than the color of its parent by exactly $$$1$$$.

Calculate the number of beautiful colorings, and print it modulo $$$998244353$$$.

Input format:
The first line contains one integer $$$n$$$ ($$$2 \le n \le 250000$$$) — the number of vertices in the tree.

Then $$$n-1$$$ lines follow, the $$$i$$$-th line contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$x_i \ne y_i$$$) denoting an edge between the vertex $$$x_i$$$ and the vertex $$$y_i$$$. These edges form a tree.

Output format:
Print one integer — the number of beautiful colorings, taken modulo $$$998244353$$$.

Constraints:
Time limit: 4.5 s
Memory limit: 512.0 MB

Example input:
5
1 2
3 2
4 2
2 5

Example output:
42

Example input:
5
1 2
2 3
3 4
4 5

Example output:
53

Editorial:
When a problem asks us to calculate the number of combinatorial objects that meet some constraints, we can sometimes use inclusion-exclusion formula. Let's try to apply it in this problem.
We could use $$$n-1$$$ constraints that should not be violated. The $$$i$$$-th constraint is formulated as follows: $$$c_i \ne c_{p_i} - 1$$$ (there will be a constraint of this type for each $$$i \in [2, n]$$$). Suppose we violated $$$k$$$ of these constraints (and have chosen which $$$k$$$ constraints to violate), then the number of colorings that meet these violations is $$$(n-k)!$$$ (for $$$k$$$ vertices, the colors on them depend on some other independent vertices, so we can assign only colors for independent vertices). So, the answer can be calculated as follows:
$$$$$$\sum\limits_{k=0}^{n-1} (-1)^k f(k) (n-k)!$$$$$$,
where $$$f(k)$$$ is the number of ways to choose $$$k$$$ constraints to violate.
One initial guess how to calculate $$$f(k)$$$ is that $$$f(k) = {{n-1}\choose{k}}$$$, as it would be calculated in other, more usual inclusion-exclusion problems. Unfortunately, in this problem, the constraints we violate are not independent. For example, if a vertex has several sons, we can violate the constraint only on at most one edge leading from a vertex to its son simultaneously, we cannot violate two or more such constraints.
Let's take care of this issue as follows: we can write a dynamic programming of the form $$$dp_{i, j}$$$ is the number of ways to process $$$i$$$ first vertices of the tree and choose exactly $$$j$$$ edges leading from these nodes to their sons so that no vertex has more than one edge leading to its sons chosen. Then, $$$dp_{n, k}$$$ is exactly the number of ways to choose $$$k$$$ edges in the tree so that no vertex has more than one chosen edge leading to its sons, and that will be equal to $$$f(k)$$$.
We can calculate this dynamic programming in a knapsack fashion in $$$O(n^2)$$$, but it is too slow. Instead, let's optimize this knapsack DP with FFT: for each vertex $$$i$$$, introduce a polynomial $$$1 + d_i \cdot x$$$, where $$$d_i$$$ is the number of children of the vertex $$$i$$$. Coefficients of this polynomial for the first vertex are the values of $$$dp_{1,k}$$$; coefficients of the product of this polynomial with the polynomial for the second vertex are the values of $$$dp_{2,k}$$$, and so on; to obtain the values of $$$dp_{n,k}$$$, we have to multiply all these polynomials, and using FFT + divide-and-conquer, we can do it in $$$O(n \log^2 n)$$$.