Problem 3030 --Bracket Sequences on Tree

3030: Bracket Sequences on Tree

"
Time Limit $20$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $1$ 正确数量 $1$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签
Cuber QQ knows about DFS on an undirected tree, he's sure that you are familiar with it too. In case you are not, Cuber QQ is delighted to share with you a snippet of pseudo code: 

function dfs(int cur, int parent):
  print(`(`)
  for all nxt that cur is adjacent to:
    dfs(nxt, cur)
  print(`)`)


You might notice that Cuber QQ print a "(" when entering a node, and a ")" when leaving a node. So when he finishes this DFS, in his console, he will see a bracket sequence of length 2n2n, where nn is the number of vertices in the tree. 

Obviously, if the tree is undirected and the nodes are unlabelled (meaning that all the nodes are treated equally), you can get a lot of different bracket sequences when you do the DFS. There are two reasons accounting for this. Firstly, when you are at cur, you can follow any permutation of the nodes that cur is adjacent to when you visit nxt. Secondly, the entrance to the tree, that is the root, is undeterministic when you start your DFS. 

So Cuber QQ couldn't help wondering how many distinct bracket sequences he can get possibly. As the answer can be very large, output it modulo 998 244 353998 244 353
The first line of the input consists of one integer tt (1≤t≤1051≤t≤105), which is the number of the test cases. 

For each test case, the tree is given in a standard format, which you might be very familiar with: first line nn (1≤n≤1051≤n≤105), the size of tree; then n−1n−1 lines, each consisting of two space-separated integers uuvv (1≤u,v≤n1≤u,v≤nu≠vu≠v), denoting an edge. 

The sum of nn from all test cases does not exceed 3.2×1063.2×106.
For each test case, output the answer in one line.
3
4
1 3
2 3
4 3
5
1 2
2 3
3 4
4 5
5
1 2
2 3
3 4
3 5
2
4
8

推荐代码 查看3030 所有题解 上传题解视频得图灵币

本题记录 用 户(点击查看用户) 运行号(点击购买题解) 时 间
算法最快[$18569 $ms] 淡意的温柔 588060 2020-05-27 09:48:22
内存最少[$78260 $KB] 淡意的温柔 588060 2020-05-27 09:48:22
第一AC 淡意的温柔 588060 2020-05-27 09:48:22
第一挑战 淡意的温柔 588060 2020-05-27 09:48:22

赛题来源/所属竞赛 2019 Multi-University Training Contest 7 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛