QOJ.ac

QOJ

Time Limit: 4 s Memory Limit: 512 MB Total points: 100
[+21]

# 8670. 独立

Statistics

给定一棵 n 个节点的树和一个正整数 m,每个节点的权值在 [1,m] 中等概率独立随机。

求这棵树的最大独立集的期望乘上 mn 后的结果。

答案对 998244353 取模。

一棵点权为 a1n 的树的最大独立集为 max,且 S 还需满足其中的任意两个点之间不存在边直接连接两者。

Input

第一行两个正整数 n,m

接下来 n-1 行,每行两个正整数,表示树的一条边。

Output

一行一个非负整数,表示答案。

Example

Input

3 2
1 2
1 3

Output

24

Explanation

比如当点权为 [2,1,1] 时,最大独立集为 2,选择 \{1\} 或者 \{2,3\} 均可。

Scoring

对于全部的数据,满足 1\le n\le 2000,1\le m\le 10^8

  • Subtask1(11pts):n,m\le 5
  • Subtask2(24pts):n,m\le 20
  • Subtask3(13pts):n,m\le 500
  • Subtask4(27pts):n\le 500
  • Subtask5(25pts):无特殊限制。