#P18307. Gona Guni

Gona Guni

Gona Guni

题目描述

给定一棵有 NN 个节点的树。你可以选取一个非空节点集合 SS,并在原树中取一个包含 SS 中所有节点、规模最小的连通子图 GG。由于原图是一棵树,GG 就是连接这些节点所需的所有简单路径的并。

定义 cost(S)cost(S) 为 GG 的最小点覆盖的大小。

图的点覆盖是一个节点集合,使每条边至少有一个端点在该集合中;最小点覆盖就是大小最小的点覆盖。只有一个节点、没有边的图,其最小点覆盖大小为 00。

给定非负整数 MM,求

$$\sum_{\varnothing\ne S\subseteq V}cost(S)^M\pmod{998244353}.$$

按整数幂的通常约定,指数为 00 时幂值为 11。

输入格式

第一行包含整数 TT,表示测试用例数。

每个测试用例的第一行包含 N,MN,M。

接下来 N−1N-1 行,每行包含两个整数 U,VU,V,表示节点 U,VU,V 之间的一条无向边。保证这些边构成一棵树。

输出格式

每个测试用例输出一行,表示答案对 998244353998244353 取模后的值。

数据范围

  • 1≤T≤30001\le T\le3000;
  • 1≤N≤3⋅1051\le N\le3\cdot10^5;
  • 0≤M≤2000\le M\le200;
  • 1≤U,V≤N1\le U,V\le N;
  • 所有测试用例的 NN 之和不超过 3⋅1053\cdot10^5。

样例

输入

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