定义唯一的 装饰 有根树$$$^{\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$$$ 构建。
示例
输入复制
541 21 33 451 21 31 41 551 22 31 44 561 22 32 42 65 6112 106 81 63 75 115 85 94 76 72 6
输出复制
411682048
注意
在第一个测试用例中,以下是四个 征服 可以构造的树以及构造每个树的一系列操作。
| 插图 | |
| ![]() |
| ![]() |
| ![]() |
| ![]() |
在第二个测试用例中,Yuuki 无法对 $$$T$$$ 应用操作,因为没有白色顶点。此外,$$$T$$$ 已经 征服 因为没有白色顶点。因此,答案是$$$1$$$。



