J. Game on tree

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

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分

2021年互联网创新创业科技节程序设计大赛

未参加
状态
已结束
规则
OI
题目
10
开始于
2021-12-23 17:30
结束于
2021-12-23 21:00
持续时间
3.5 小时
主持人
参赛人数
98