#1919. 黑白树

    ID: 1919 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 提高 上传者: 标签>CTT赛事:contest1972来源:qoj.ac数据:公开样例概率期望

黑白树

黑白树

题目描述

标题: 黑白树 - Problem - QOJ.ac

#10354. 黑白树

Statistics

The problem was used in the following contests:

给定一棵 n 个点的树,每个点有 50% 的概率为黑点,50% 的概率为白点。

给定正整数 m,等概率随机选出一个边集(即每条边有 50% 的概率在边集中),记边集大小为 x。若对于边集中的每条边,都满足这条边两侧的黑点个数不同,则得分为 mx,否则得分为 0。

你需要求出期望得分。

有多组数据。

输入格式

第一行一个正整数 t 表示数据组数。

每组数据第一行两个正整数 n,m。接下来 n−1 行每行两个正整数 u,v 表示一条边。

输出格式

对于每组数据,输出一行一个整数表示期望得分×22n−1对998244353取模的结果。

样例数据

样例输入

2
3 5
1 2
2 3
10 23333333
3 1
4 2
6 7
8 6
2 5
3 6
10 1
9 7
1 2

样例输出

158
167850015

子任务

对于10%的数据,n≤10。

对于20%的数据,n≤20。

对于30%的数据,n≤200。

对于40%的数据,n≤1000。

对于50%的数据,n≤3000。

对于60%的数据,n≤10000。

对于70%的数据,n≤15000。

对于100%的数据,t≤5,2≤n≤20000,∑n≤70000,1≤m<998244353,1≤u,v≤n。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

2
3 5
1 2
2 3
10 23333333
3 1
4 2
6 7
8 6
2 5
3 6
10 1
9 7
1 2
158
167850015