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

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

题目描述

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

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

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

输入格式

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

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

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

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

输出格式

输出 11 行:

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

样例

样例输入

4 1 2
1 2
2 3
3 4

样例输出

4

数据范围与提示

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

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

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