J. Game on tree

时间限制：4s

空间限制：256MB

本题分值：700

题目描述

现有一棵由 \(n\) 个结点组成的树， 根节点为 1 。

树的每个结点上有一个数字\(p_i\)，且 \((p_1,p_2...,p_n)\) 是 \((1,2,...n)\) 的一个排列，即 它们不重复也不遗漏地取遍了\(1,2,...n\)中的所有数 。

现在，高木同学和西片进行游戏，游戏规则如下：

• 西片优先选择一个位置放置棋子
• 如果结点 \(x\) 有孩子 \(c\) ，且 \(p_x-p_c=1\) ，则棋子可以从 \(x\) 走到 \(c\)。
• 在一轮中：
  • 西片按照上一条规则将棋子移动一步。如果无路可走，则判负。
  • 高木按照上一条规则将棋子移动一步。如果无路可走，则判负。

问，有多少种分配结点上数字 \((p_1,p_2,...,p_n)\) 的方法，使得 \((p_1,p_2,...,p_n)\) 是一个排列，且西片无论选择怎样的初始位置和怎样的走棋策略，高木同学总可以获胜。

由于答案可能过大，对\(998244353\)取模。

输入格式

第一行一个整数\(n\)，表示树的结点数目。

接下来\(n-1\)行每行两个整数，表示树的一条边。

输出格式

输出对应的答案，注意取模。

样例输入1

3
1 2
1 3

样例输出1

2

样例1解释

其中一种分配方案：\((1,2,3)\)，即结点\(1\)分配数字\(1\)，结点\(2\)分配数字\(2\)，结点\(3\)分配数字\(3\)。

无论西片选择怎样的初始位置，都无法向其他边移动，所以高木同学一定会获胜。

样例输入2

6
1 4
2 6 
5 1
4 3
2 5

样例输出2

298

样例输入3

10
1 2
2 3
3 4 
4 5
5 6
6 7
7 8
8 9
9 10

样例输出3

1468457

数据范围及限制

边 \(u,v\) 满足 \(1\le u,v\le n\)，且保证给出的一定是一棵树。

测试点编号	n	其他约定	测试点分值
1	\(n=3\)		每个测试点40分
2~3	\(1\le n\le 9\)		每个测试点50分
4~5	\(1\le n\le 1000\)	给出的一定是一条链	每个测试点80分
6~7	\(1\le n\le 1000\)		每个测试点100分
8~9	\(1\le n\le 2*10^5\)		每个测试点100分