CF2229E.Deconstruction Tree

A tree with $n$ nodes fell from the sky along with an initially empty set $S$. Ecstatic by this unlikely event, you do the following $n - 1$ times:

• let $x$ be the leaf with maximum index.
• add $x$ into $S$ (note that if $x$ is already in $S$ then nothing changes).
• select any leaf other than $x$ and remove it from the tree.

Determine the number of distinct sets $S$ you can make. As the number could be ginormous, output it modulo $998\,244\,353$.

一棵包含 $n$ 个节点的树从天而降，同时还有一个初始为空的集合 $S$。你欣喜若狂，于是执行以下操作 $n - 1$ 次：

• 设 $x$ 为编号最大的叶子节点；
• 将 $x$ 加入集合 $S$（注意：若 $x$ 已在 $S$ 中，则不作任何改变）；
• 任选一个不同于 $x$ 的叶子节点，并将其从树中移除。

求你能得到的不同集合 $S$ 的数量。由于该数量可能极大，请对 $998\,244\,353$ 取模后输出。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each testcase contains an integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the size of the tree.

Then $n - 1$ lines follow, each of which contain two integers $u$ and $v$ ($1 \le u,v \le n, u \ne v$), which describe a pair of vertices connected by an edge. It is guaranteed that the given graph is a tree.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

Output the number of distinct sets that can be obtained modulo $998\,244\,353$.

输出模 $998\,244\,353$ 意义下可得到的不同集合的数量。

For the first testcase, there is only one possible order: $1$, making the set ${2}$

For the third testcase, the tree looks as follows:

you can make the sets:

• ${3, 6, 7}$ by removing in the order $1, 2, 3, 4, 5, 6$
• ${3, 4, 6, 7}$ by removing in the order $2, 1, 3, 4, 5, 6$
• ${3, 4, 5, 6, 7}$ by removing in the order $2, 3, 1, 4, 5, 6$

It can be proven that these are the only sets obtainable.

对于第一个测试用例，只存在一种可能的删除顺序：$1$，从而得到集合 ${2}$。

对于第三个测试用例，树的结构如下所示：

你可以通过以下删除顺序得到如下集合：

• 按顺序 $1, 2, 3, 4, 5, 6$ 删除，得到集合 ${3, 6, 7}$；
• 按顺序 $2, 1, 3, 4, 5, 6$ 删除，得到集合 ${3, 4, 6, 7}$；
• 按顺序 $2, 3, 1, 4, 5, 6$ 删除，得到集合 ${3, 4, 5, 6, 7}$。

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