黑白染色
题目描述
给定一颗 n 个点的树,和一个数 c,现在我们要把这棵树的所有点和边黑白染色,也就是一共有 22n−1 种方案。我们称一种染色方案是合法的当且仅当对于所有黑色的边,其两边的两颗子树内的黑色的点数量不同。
对于一种有 t 个黑边的树,它的权值是 ct 。请你求出所有合法的方案中树的权值之和是多少。答案对 998244353 取模。
输入格式
第一行两个数 n,c 。
接下来 n−1 行每行两个整数 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 。
| 测试点编号 |
n≤ |
特殊性质 |
| 1∼2 |
9 |
无 |
| 3∼4 |
18 |
| 5∼10 |
100 |
| 11∼12 |
2000 |
A |
| 13∼16 |
B |
| 17∼20 |
无 |
性质 A:保证这棵树的边分别为 (1,2),(2,3),(3,4),…,(n−1,n) ;
性质 B:保证 c=1 。