← 返回题目列表

Codeforces · 1857/G

G. 计数图表

中文机器翻译题面 查看原题

给定一棵由 $$$n$$$ 顶点组成的树。树是无环的连通无向图。树的每条边都有其权重 $$$w_i$$$。

您的任务是计算满足所有四个条件的不同图表的数量:

1. 该图没有自环和重边。
2. 图边上的权重为整数,且不超过$$$S$$$。
3. 该图恰好有一个最小生成树。
4. 图的最小生成树是给定的树。

如果两个图的边集不同,则考虑到边的权重,则认为两个图不同。

答案可能很大,输出它对 $$$998244353$$$ 取模。

输入

第一行包含一个整数 $$$t$$$ ($$$1\le t\le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$S$$$ ($$$2 \le n \le 2 \cdot 10^5, 1\le S\le 10^9$$$) - 顶点数量和权重上限。

然后沿着描述树的 $$$n-1$$$ 行,第 $$$i$$$ 行包含三个整数 $$$u_i$$$、$$$v_i$$$ 和 $$$w_i$$$ ($$$1\le u_i,v_i\le n, u_i \ne v_i, 1\le w_i\le S$$$) — 一条边在权重为 $$$w_i$$$ 的树中。

保证所有测试的$$$n$$$总和不超过$$$2\cdot 10^5$$$。

输出

对于每个测试,输出满足条件的不同图的数量,以 $$$998244353$$$ 为模。

示例

输入 #1

4
2 5
1 2 4
4 5
1 2 2
2 3 4
3 4 3
5 6
1 2 3
1 3 2
3 4 6
3 5 1
10 200
1 2 3
2 3 33
3 4 200
1 5 132
5 6 1
5 7 29
7 8 187
7 9 20
7 10 4

输出 #1

1
8
80
650867886

注意

在第一个示例中,只有一个图,即给定的树。

在第二个示例中,给定的树如下所示: