CF1172B Nauuo and Circle
题目描述
给定 $n$ 个节点。它们按照输入连成一棵树。
现在要将这棵树放到圆上。具体地,找到一个排列 $p_1, p_2, \cdots, p_n$,钦定圆最上方为第 $1$ 个点,之后所有点按顺时针排列。第 $i$ 个点对应节点 $p_i$。如果存在树边 $(p_u, p_v)$,则在圆上连接点 $u, v$。
一棵树是合法的,当且仅当这棵树在圆中无交叉的边(两边共用一端点除外)。
求合法树的方案总数,对 $998244353$ 取模。
注意:定义两个方案是不同的,当且仅当存在 $1 \le i \le n$,两个方案的 $p_i$ 不同。
输入格式
第一行一个整数 $n$。
之后 $n - 1$ 行,每行两个整数 $u, v$,描述树边 $(u, v)$。
保证输入的边构成一棵树。
输出格式
输出方案总数,对 $998244353$ 取模。
说明/提示
#### 样例 $1$ 解释
所有方案如下:

下面是一个非法方案,$(1, 3)$ 和 $(2, 4)$ 交叉了:

#### 样例 $2$ 解释
所有方案均合法,总数为 $4! = 24$。
#### 数据范围
- $2 \le n \le 2 \cdot 10^5$。