问题2512--圆上画树(circle)

2512: 圆上画树(circle)

时间限制: 1 Sec  内存限制: 128 MB
提交: 5  解决: 4
[提交] [状态] [讨论版] [命题人:]

题目描述

BSNY画了一个圆,他还想在圆上画n个点的树,n个点都在圆的轮廓线上,要求树的边没有相交。n个点的编号为1~n,已在圆上均匀的画了n个小圈,问有多少种方式可以将n个小圈内填充1~n的编号,使得树的边没有相交(端点相交不算相交)。
例如n=4,边为(1, 2), (1, 3), (2, 4)
符合要求的填充方式有16种,具体如下图:


但下图情况不符合要求,因为(1, 3)和(2, 4)相交了:


输入

第一行输入n
接下来n-1行输入n-1条边(保证是一棵树)

输出

输出方案数,答案需要取模998244353

样例输入 Copy

4
1 2
1 3
1 4

样例输出 Copy

24

提示

30%数据   2<=n<=20
60%数据   2<=n<=2000
100%数据  2<=n<=2*10^5

来源/分类