#P18307. Gona Guni
Gona Guni
Gona Guni
题目描述
给定一棵有 个节点的树。你可以选取一个非空节点集合 ,并在原树中取一个包含 中所有节点、规模最小的连通子图 。由于原图是一棵树, 就是连接这些节点所需的所有简单路径的并。
定义 为 的最小点覆盖的大小。
图的点覆盖是一个节点集合,使每条边至少有一个端点在该集合中;最小点覆盖就是大小最小的点覆盖。只有一个节点、没有边的图,其最小点覆盖大小为 。
给定非负整数 ,求
$$\sum_{\varnothing\ne S\subseteq V}cost(S)^M\pmod{998244353}.$$按整数幂的通常约定,指数为 时幂值为 。
输入格式
第一行包含整数 ,表示测试用例数。
每个测试用例的第一行包含 。
接下来 行,每行包含两个整数 ,表示节点 之间的一条无向边。保证这些边构成一棵树。
输出格式
每个测试用例输出一行,表示答案对 取模后的值。
数据范围
- ;
- ;
- ;
- ;
- 所有测试用例的 之和不超过 。
样例
输入
2
3 1
1 2
1 3
20 200
1 2
1 3
2 4
1 5
5 6
1 7
6 8
6 9
3 10
4 11
6 12
11 13
4 14
13 15
15 16
6 17
13 18
15 19
13 20
输出
4
286430678