← 返回题目列表

Codeforces · 2178/F

F. 征服或森林

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

定义唯一的 装饰 有根树$$$^{\text{*}}$$$ 的着色为以下顶点着色:

  • 如果以 $$$v$$$ 为根的子树 $$$^{\text{†}}$$$ 中的顶点数为偶数,则顶点 $$$v$$$ 被着色为白色;
  • 否则,$$$v$$$ 被涂成黑色。

在征服圣诞树森林的过程中,Yuuki 遇到了一个 装饰性 彩色树 $$$T$$$,其 $$$n$$$ 顶点标记为从 $$$1$$$ 到 $$$n$$$,根于顶点 $$$1$$$。

Yuuki 考虑着这棵树 征服 当且仅当 至少一个 满足以下条件:

  • 树中没有白色顶点,或者
  • 存在一些顶点$$$v$$$,使得所有白色顶点都位于从根$$$1$$$到$$$v$$$的简单路径上。

To 征服 树,Yuuki 可以对 $$$T$$$ 应用以下操作任意次数(可能为零):

  • 首先,选择一个顶点 $$$w$$$,其颜色为白色,并且 不 $$$T$$$ 的根。让 $$$p_w$$$ 成为 $$$w$$$ 的父级。
  • 然后,删除连接 $$$p_w$$$ 和 $$$w$$$ 的边,并在之间添加一条边 任何 两个顶点,使得 $$$T$$$ 仍然是一棵树。
  • 最后,重新着色 $$$T$$$ 的顶点,使其成为 装饰性 彩色。请注意,$$$T$$$ 始终以顶点 $$$1$$$ 为根。
第一个测试用例中操作的可能应用。结果树是 征服 因为所有白色顶点都位于顶点 $$$1$$$ 和 $$$3$$$ 之间的路径上。

计算不同$$$^{\text{‡}}$$$的数量 Yuuki 可以通过对 $$$T$$$ 应用上述操作任意次数来构建 征服 树。由于答案可能很大,因此输出它对 $$$998\,244\,353$$$ 取模。

请注意,Yuuki 不能在操作中途停止(特别是,他必须在检查树是否为树之前重新着色) 征服)。此外,即使树已经存在,Yuuki 也可以应用该操作 征服.

$$$^{\text{*}}$$$树是没有环的连通图。

$$$^{\text{†}}$$$顶点 $$$v$$$ 的子树是 $$$v$$$ 的子图、其所有后代以及它们之间的所有边。

$$$^{\text{‡}}$$$当且仅当存在一对顶点,并且其中一棵树中它们之间存在边,而另一棵树中没有边时,两棵树才被认为是不同的。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2\le n\le 2\cdot 10^5$$$) — $$$T$$$ 中的顶点数。

然后是 $$$n-1$$$ 行,第 $$$i$$$ 行包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1\le u_i \lt v_i\le n$$$) — 第 $$$i$$$ 条边连接的两个顶点。

保证给定的边形成一棵树。

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

输出

对于每个测试用例,输出一个整数 - 不同的数量 征服 树可以由 $$$T$$$ 模 $$$998\,244\,353$$$ 构建。

示例

输入
复制

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

输出
复制

4
1
16
8
2048

注意

在第一个测试用例中,以下是四个 征服 可以构造的树以及构造每个树的一系列操作。

说明
插图
  • 该操作应用零次。
  • 给定的树已经 征服 因为所有白色顶点都位于顶点 $$$1$$$ 和 $$$4$$$ 之间的简单路径上。
  • 第一个也是唯一的操作选择 $$$w$$$ 作为顶点 $$$3$$$ ($$$p_w$$$ 是顶点 $$$1$$$)并在顶点 $$$2$$$ 和 $$$4$$$ 之间绘制一条边。
  • 生成的树是 征服 因为所有白色顶点都位于顶点 $$$1$$$ 和 $$$3$$$ 之间的简单路径上。
  • 第一个也是唯一的操作选择 $$$w$$$ 作为顶点 $$$3$$$ ($$$p_w$$$ 是顶点 $$$1$$$)并在顶点 $$$2$$$ 和 $$$3$$$ 之间绘制一条边。
  • 生成的树是 征服 因为所有白色顶点都位于顶点 $$$1$$$ 和 $$$3$$$ 之间的简单路径上。
  • 第一个操作选择 $$$w$$$ 作为顶点 $$$3$$$ ($$$p_w$$$ 是顶点 $$$1$$$),并在顶点 $$$2$$$ 和 $$$4$$$ 之间绘制一条边。
  • 第二个操作选择 $$$w$$$ 作为顶点 $$$4$$$ ($$$p_w$$$ 是顶点 $$$2$$$),并在顶点 $$$1$$$ 和 $$$4$$$ 之间绘制一条边。
  • 生成的树是 征服 因为所有白色顶点都位于顶点 $$$1$$$ 和 $$$4$$$ 之间的简单路径上。

在第二个测试用例中,Yuuki 无法对 $$$T$$$ 应用操作,因为没有白色顶点。此外,$$$T$$$ 已经 征服 因为没有白色顶点。因此,答案是$$$1$$$。