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$ 解释 所有方案如下: ![](https://espresso.codeforces.com/4bbeb64c560c5faab632ae54f8543dbda91b3145.png) 下面是一个非法方案,$(1, 3)$ 和 $(2, 4)$ 交叉了: ![](https://espresso.codeforces.com/28c77a9b93eca97a2911d8fe525f9bed5cf5a027.png) #### 样例 $2$ 解释 所有方案均合法,总数为 $4! = 24$。 #### 数据范围 - $2 \le n \le 2 \cdot 10^5$。