#6391. 「THUPC2018」淘米神的树 / Tommy

内存限制:512 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: diamond_duke

题目描述

可爱的 Tommy 有一棵树。这棵树上只有点 a b 是黑色,其它的点都是白色。

每次,Tommy 可以将一个黑色 p 的点染成红色,然后把和 p 相邻的所有白色的点染成黑色。最后,所有的点都会被染成红色。

设第 i 个点是第 t_i 个被染成红色的,那么 t_i 是一个 1 n 的排列。Tommy 希望你帮他求出,有多少种不同的 t_i

输入格式

每个输入文件仅包含一个测试数据。

  • 第一行三个用空格隔开的正整数 n,a,b ,表示树的点数和初始的黑色点的编号;

  • 接下来 n-1 行,每行两个正整数 x,y 描述树上的一条边 \left( x,y\right)

树上的节点从 1 开始编号。

输出格式

输出 1 行:

  • 一个整数,表示不同的排列 t_i 的个数除以 998,244,353 的余数。

样例

样例输入

4 1 2
1 2
2 3
3 4

样例输出

4

数据范围与提示

保证 a,b\le n\le 234,567

来自 2018 清华大学学生程序设计竞赛暨高校邀请赛(THUPC2018),感谢 Pony.ai 对此次比赛的支持。

题解等资源可在 https://github.com/wangyurzee7/THUPC2018 查看。