CF1010F.Tree

NOI/NOI+/CTSC

通过率：0%

时间限制：7.00s

内存限制：256MB

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

The Main Martian Tree grows on Mars. It is a binary tree (a rooted tree, with no more than two sons at each vertex) with $n$ vertices, where the root vertex has the number $1$ . Its fruits are the Main Martian Fruits. It's summer now, so this tree does not have any fruit yet.

Autumn is coming soon, and leaves and branches will begin to fall off the tree. It is clear, that if a vertex falls off the tree, then its entire subtree will fall off too. In addition, the root will remain on the tree. Formally: the tree will have some connected subset of vertices containing the root.

After that, the fruits will grow on the tree (only at those vertices which remain). Exactly $x$ fruits will grow in the root. The number of fruits in each remaining vertex will be not less than the sum of the numbers of fruits in the remaining sons of this vertex. It is allowed, that some vertices will not have any fruits.

Natasha wondered how many tree configurations can be after the described changes. Since this number can be very large, output it modulo $998244353$ .

Two configurations of the resulting tree are considered different if one of these two conditions is true:

they have different subsets of remaining vertices;
they have the same subset of remaining vertices, but there is a vertex in this subset where they have a different amount of fruits.

主火星树生长在火星上。它是一棵二叉树（即一棵有根树，每个顶点至多有两个子节点），共有 $n$ 个顶点，其中根节点编号为 $1$ 。它的果实称为主火星果实。现在正值夏季，因此该树上尚无任何果实。

秋季即将来临，树叶与枝条将开始从树上脱落。显然，若某个顶点从树上脱落，则其整个子树也将随之脱落。此外，根节点必定保留在树上。形式化地：最终树将保留一个包含根节点的、连通的顶点子集。

随后，果实将在树上生长（仅在那些保留下来的顶点上）。根节点上恰好生长 $x$ 个果实。对于每个保留下来的顶点，其果实数量不少于其所有保留下来的子节点的果实数量之和。允许某些顶点上不生长任何果实。

娜塔莎想知道：经过上述变化后，可能形成的树的构型总数是多少？由于该数可能非常大，请输出其对 $998244353$ 取模的结果。

若以下任一条件成立，则认为两个最终树的构型不同：

它们所保留的顶点子集不同；
它们所保留的顶点子集相同，但存在某个顶点，在该顶点上的果实数量不同。

输入格式

The first line contains two integers: $n$ and $x$ ( $1 \le n \le 10^5$ , $0 \le x \le 10^{18}$ ) — the size of the tree and the number of fruits in the root.

The $i$ -th of the following $(n-1)$ lines contains two integers $a_i$ and $b_i$ ( $1 \le a_i, b_i \le n$ ) — vertices connected by the $i$ -th edge of the tree.

It is guaranteed that the input data describes a correct binary tree with the root at the vertex $1$ .

第一行包含两个整数： $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$ 为根的合法二叉树。

输出格式

Print one number — the number of configurations of the resulting tree modulo $998244353$ .

输出一个数字——结果树的构型数量对 $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
```

说明/提示

Consider the first example.

There are $2$ fruits at the vertex $1$ . The following $13$ options are possible:

there is no vertex $2$ , there is no vertex $3$ ;
there is no vertex $2$ , there are no fruits at the vertex $3$ ;
there is no vertex $2$ , there is $1$ fruit at the vertex $3$ ;
there is no vertex $2$ , there are $2$ fruits at the vertex $3$ ;
there are no fruits at the vertex $2$ , there is no vertex $3$ ;
there are no fruits at the vertex $2$ , there are no fruits at the vertex $3$ ;
there are no fruits at the vertex $2$ , there is $1$ fruit at the vertex $3$ ;
there are no fruits at the vertex $2$ , there are $2$ fruits at the vertex $3$ ;
there is $1$ fruit at the vertex $2$ , there is no vertex $3$ ;
there is $1$ fruit at the vertex $2$ , there are no fruits at the vertex $3$ ;
there is $1$ fruit at the vertex $2$ , there is $1$ fruit at the vertex $3$ ;
there are $2$ fruits at the vertex $2$ , there is no vertex $3$ ;
there are $2$ fruits at the vertex $2$ , there are no fruits at the vertex $3$ .