#P18915. [2026多校联测]黑白染色

[2026多校联测]黑白染色

黑白染色

题目描述

给定一颗 n n 个点的树,和一个数 c c ,现在我们要把这棵树的所有点和边黑白染色,也就是一共有 22n−1 2^{2n-1} 种方案。我们称一种染色方案是合法的当且仅当对于所有黑色的边,其两边的两颗子树内的黑色的点数量不同。

对于一种有 t t 个黑边的树,它的权值是 ct c^t 。请你求出所有合法的方案中树的权值之和是多少。答案对 998244353998244353 取模。

输入格式

第一行两个数 n,c n, c 。

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

输出格式

一行一个数表示答案。

样例

输入1

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

输出1

2616949

数据范围

对于所有数据保证, 1≤n≤2000,1≤c≤109 1 \leq n \leq 2000, 1 \leq c \leq 10^9 。

测试点编号 n≤ n \leq 特殊性质
1∼21 \sim 2 99 无
3∼43 \sim 4 1818
5∼105 \sim 10 100100
11∼1211 \sim 12 20002000 A
13∼1613 \sim 16 B
17∼2017 \sim 20 无

性质 A:保证这棵树的边分别为 (1,2),(2,3),(3,4),…,(n−1,n) (1, 2), (2, 3), (3, 4), \dots, (n-1, n) ;
性质 B:保证 c=1 c = 1 。