CF1613F Tree Coloring

给定一棵有 $n$ 个顶点的有根树，顶点编号为 $1$ 到 $n$，树的根为顶点 $1$。 你需要将树的所有顶点染成 $n$ 种颜色（颜色编号为 $1$ 到 $n$），使得每种颜色恰好有一个顶点。设 $c_i$ 表示顶点 $i$ 的颜色，$p_i$ 表示顶点 $i$ 在有根树中的父节点。如果不存在顶点 $k$（$k > 1$），满足 $c_k = c_{p_k} - 1$，即不存在某个顶点的颜色比其父节点的颜色恰好小 $1$，则称这种染色是美丽的。 请计算美丽染色的方案数，并将答案对 $998244353$ 取模后输出。

第一行包含一个整数 $n$（$2 \le n \le 250000$），表示树的顶点数。 接下来 $n-1$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$1 \le x_i, y_i \le n$，$x_i \ne y_i$），表示树中的一条边。这些边构成一棵树。

输出一个整数，表示美丽染色的方案数，对 $998244353$ 取模。

由 ChatGPT 4.1 翻译