← 返回题目列表

Codeforces · 1010/F

F. 树

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

主火星树生长在火星上。它是一棵二叉树(有根树,每个顶点不超过两个儿子),有 $$$n$$$ 个顶点,其中根顶点的编号为 $$$1$$$。它的果实是主要的火星水果。现在是夏天,这棵树还没有结果子。

秋天即将来临,树叶和树枝将开始从树上掉落。很明显,如果一个顶点从树上脱落,那么它的整个子树也会脱落。此外,根将保留在树上。形式上:树将具有一些包含根的连通顶点子集。

之后,果实将在树上生长(仅在剩余的顶点上)。根部将会生长出 $$$x$$$ 的果实。剩余每个顶点中的水果数量将不小于该顶点剩余子节点中的水果数量之和。允许某些顶点没有任何水果。

Natasha 想知道在所描述的更改之后可以有多少种树配置。由于这个数字可能非常大,因此输出它对 $$$998244353$$$ 取模。

如果这两个条件之一为真,则结果树的两种配置被认为是不同的:

- 它们具有不同的剩余顶点子集;
- 它们具有相同的剩余顶点子集,但在该子集中有一个顶点,它们具有不同数量的水果。

输入

第一行包含两个整数:$$$n$$$ 和 $$$x$$$ ($$$1 \le n \le 10^5$$$, $$$0 \le x \le 10^{18}$$$) — 树的大小和根中果实的数量。

以下 $$$(n-1)$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$) — 由树的第 $$$i$$$ 边连接的顶点。

保证输入数据描述正确的二叉树,根位于顶点$$$1$$$。

输出

打印一个数字——生成的树的配置数量对 $$$998244353$$$ 取模。

示例

输入 #1

3 2
1 2
1 3

输出 #1

13

输入 #2

2 5
1 2

输出 #2

7

输入 #3

4 10
1 2
1 3
3 4

输出 #3

441

注意

考虑第一个例子。

顶点$$$1$$$处有$$$2$$$个水果。以下 $$$13$$$ 选项是可能的:

- 没有顶点$$$2$$$,没有顶点$$$3$$$;
- 没有顶点$$$2$$$,顶点$$$3$$$没有水果;
- 没有顶点$$$2$$$,顶点$$$3$$$有$$$1$$$水果;
- 没有顶点$$$2$$$,顶点$$$3$$$有$$$2$$$水果;
- 顶点$$$2$$$处没有水果,没有顶点$$$3$$$;
- 顶点$$$2$$$没有水果,顶点$$$3$$$没有水果;
- 顶点$$$2$$$没有水果,顶点$$$3$$$有$$$1$$$水果;
- 顶点$$$2$$$没有水果,顶点$$$3$$$有$$$2$$$水果;
- 顶点$$$2$$$处有$$$1$$$水果,没有顶点$$$3$$$;
- 顶点$$$2$$$有$$$1$$$水果,顶点$$$3$$$没有水果;
- 顶点$$$2$$$有$$$1$$$水果,顶点$$$3$$$有$$$1$$$水果;
- 顶点$$$2$$$处有$$$2$$$水果,没有顶点$$$3$$$;
- 顶点$$$2$$$有$$$2$$$水果,顶点$$$3$$$没有水果。

考虑第二个例子。顶点 $$$1$$$ 有 $$$5$$$ 水果。以下 $$$7$$$ 选项是可能的:

- 没有顶点$$$2$$$;
- 顶点 $$$2$$$ 处没有水果;
- 顶点$$$2$$$处有$$$1$$$水果;
- 顶点$$$2$$$有$$$2$$$水果;
- 顶点$$$2$$$有$$$3$$$水果;
- 顶点$$$2$$$有$$$4$$$水果;
- 顶点 $$$2$$$ 有 $$$5$$$ 水果。