← 返回题目列表

Codeforces · 1930/G

G. 前缀最大设置计数

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

定义一个函数 $$$f$$$,使得对于数组 $$$b$$$,$$$f(b)$$$ 返回前缀最大值为 $$$b$$$ 的数组。换句话说, $$$f(b)$$$ 是一个仅包含 $$$b_i$$$ 元素的数组,其中 $$$b_i=\max(b_1,b_2,\ldots,b_i)$$$,而不改变它们的顺序。例如,$$$f([3,10,4,10,15,1])=[3,10,10,15]$$$。

给你一棵由 $$$n$$$ 节点组成的树,根节点为 $$$1$$$。

如果对于所有 $$$i$$$ 满足以下条件,则 $$$^\dagger$$$ $$$p$$$ 的排列被视为树的前序:

- 令 $$$k$$$ 为节点 $$$p_i$$$ 的真后代 $$$^\ddagger$$$ 的数量。
- 对于所有$$$x$$$,使得$$$i < x \leq i+k$$$,$$$p_x$$$ 是节点$$$p_i$$$ 的真后代。

找出所有可能的预购 $$$a$$$ 中 $$$f(a)$$$ 的不同值的数量。由于该值可能很大,因此您只需对 $$$998\,244\,353$$$ 求模即可。

$$$^\dagger$$$ 长度 $$$n$$$ 的排列是一个数组,由 $$$n$$$ 不同的整数组成,从 $$$1$$$ 到 $$$n$$$ 的任意顺序。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。

$$$^\ddagger$$$ 节点 $$$t$$$ 是节点 $$$s$$$ 的真后代,如果 $$$s \neq t$$$ 和 $$$s$$$ 位于从 $$$t$$$ 到 $$$1$$$ 的唯一简单路径上。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$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$$$ 可以得到的不同值的数量。

示例

输入 #1

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

输出 #1

1
1
2
1
8
6

注意

在第一个测试用例中,唯一有效的预订是 $$$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]$$$.