← 返回题目列表

Codeforces · 2229/E

E. 解构树

中文机器翻译题面 查看原题

一棵具有 $$$n$$$ 节点的树以及最初为空的集合 $$$S$$$ 从天而降。对于这个不太可能发生的事件,您欣喜若狂,执行了以下 $$$n - 1$$$ 次:

  • 令 $$$x$$$ 为具有最大索引的叶子。
  • 将 $$$x$$$ 添加到 $$$S$$$ 中(请注意,如果 $$$x$$$ 已经在 $$$S$$$ 中,则不会发生任何变化)。
  • 选择 $$$x$$$ 以外的任何叶子并将其从树中删除。

确定您可以制作的不同集合 $$$S$$$ 的数量。由于数字可能很大,因此输出它对 $$$998\,244\,353$$$ 取模。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 树的大小。

接下来是 $$$n - 1$$$ 行,每行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u,v \le n, u \ne v$$$),它们描述由边连接的一对顶点。保证给定的图是一棵树。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

输出可以以 $$$998\,244\,353$$$ 为模获得的不同集合的数量。

示例

输入
复制

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

输出
复制

1
1
3
13
1
1

注意

对于第一个测试用例,只有一个可能的顺序:$$$1$$$,使得集合 $$$\{2\}$$$

对于第三个测试用例,树如下所示:

您可以进行以下设置:

  • $$$\{3, 6, 7\}$$$ 按顺序删除 $$$1, 2, 3, 4, 5, 6$$$
  • $$$\{3, 4, 6, 7\}$$$ 按顺序删除 $$$2, 1, 3, 4, 5, 6$$$
  • $$$\{3, 4, 5, 6, 7\}$$$ 按顺序删除 $$$2, 3, 1, 4, 5, 6$$$

可以证明这些是唯一可以获得的集合。