CF1930G Prefix Max Set Counting

定义一个函数 $f$，对于一个数组 $b$，$f(b)$ 返回 $b$ 的前缀最大值数组。换句话说，$f(b)$ 是一个只包含那些 $b_i = \max(b_1, b_2, \ldots, b_i)$ 的元素的数组，且不改变它们的顺序。例如，$f([3,10,4,10,15,1]) = [3,10,10,15]$。 给定一棵以 $1$ 为根的 $n$ 个节点的树。 一个排列 $^\dagger$ $p$ 被称为该树的先序遍历，如果对于所有 $i$，满足以下条件： - 设 $k$ 为节点 $p_i$ 的真后代 $^\ddagger$ 的数量。 - 对于所有 $x$ 满足 $i < x \leq i+k$，$p_x$ 是节点 $p_i$ 的真后代。 请你求出所有可能的先序遍历 $a$ 中，$f(a)$ 的不同取值的个数。由于答案可能很大，只需输出对 $998\,244\,353$ 取模的结果。 $^\dagger$ 长度为 $n$ 的排列是一个由 $1$ 到 $n$ 的 $n$ 个互不相同的整数按任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是（$2$ 出现了两次），$[1,3,4]$ 也不是（$n=3$ 但出现了 $4$）。 $^\ddagger$ 如果 $s \neq t$ 且 $s$ 在从 $t$ 到 $1$ 的唯一简单路径上，则称节点 $t$ 是节点 $s$ 的真后代。

每个测试点包含多组测试数据。第一行为一个整数 $t$（$1 \leq t \leq 10^5$）——表示测试用例的数量。接下来是每组测试数据的描述。 每组测试数据的第一行为一个整数 $n$（$1 \leq n \leq 10^6$）——表示节点数。 接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \leq u, v \leq n$，$u \neq v$），表示 $u$ 和 $v$ 之间有一条边。保证所给的边构成一棵树。 保证所有测试用例中 $n$ 的总和不超过 $10^6$。

对于每组测试数据，输出所有可能的 $f(a)$ 的不同取值的个数，对 $998\,244\,353$ 取模。

在第一个测试用例中，唯一的先序遍历为 $a=[1]$，因此唯一可能的 $f(a)$ 为 $[1]$。 在第二个测试用例中，唯一的先序遍历为 $a=[1,2]$，因此唯一可能的 $f(a)$ 为 $[1,2]$。 在第三个测试用例中，两个合法的先序遍历为 $a=[1,2,3]$ 和 $a=[1,3,2]$，因此可能的 $f(a)$ 为 $[1,2,3]$ 和 $[1,3]$。 在第五个测试用例中，可能的 $f(a)$ 为： - $[1,5]$； - $[1,2,5]$； - $[1,3,5]$； - $[1,4,5]$； - $[1,2,3,5]$； - $[1,2,4,5]$； - $[1,3,4,5]$； - $[1,2,3,4,5]$。 由 ChatGPT 4.1 翻译