#1919. 黑白树
黑白树
黑白树
题目描述
标题: 黑白树 - Problem - QOJ.ac
#10354. 黑白树
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