CF1857G.Counting Graphs

Given a tree consisting of $n$ vertices. A tree is a connected undirected graph without cycles. Each edge of the tree has its weight, $w_i$.

Your task is to count the number of different graphs that satisfy all four conditions:

1. The graph does not have self-loops and multiple edges.
2. The weights on the edges of the graph are integers and do not exceed $S$.
3. The graph has exactly one minimum spanning tree.
4. The minimum spanning tree of the graph is the given tree.

Two graphs are considered different if their sets of edges are different, taking into account the weights of the edges.

The answer can be large, output it modulo $998244353$.

给定一棵包含 $n$ 个顶点的树。树是一种无环的连通无向图。树的每条边都有一个权值 $w_i$。

你的任务是计算满足以下四个条件的不同图的个数：

1. 图中不含自环和重边。
2. 图中各边的权值为整数，且不超过 $S$。
3. 图恰好存在一棵最小生成树。
4. 该图的最小生成树恰好是给定的这棵树。

若两个图的边集（含边权）不同，则认为它们是不同的图。

答案可能很大，请对 $998244353$ 取模后输出。

The first line contains an integer $t$ ($1\le t\le 10^4$) — the number of test cases.

The first line of each test case contains two integers $n$ and $S$ ($2 \le n \le 2 \cdot 10^5, 1\le S\le 10^9$) — the number of vertices and the upper bound of the weights.

Then follow $n-1$ lines describing the tree, the $i$-th line contains three integers $u_i$, $v_i$, and $w_i$ ($1\le u_i,v_i\le n, u_i \ne v_i, 1\le w_i\le S$) — an edge in the tree with weight $w_i$.

It is guaranteed that the sum of $n$ for all tests does not exceed $2\cdot 10^5$.

第一行包含一个整数 $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$。

For each test, output the number of different graphs that satisfy the conditions, modulo $998244353$.

对于每组测试，输出满足条件的不同图的数量，对 $998244353$ 取模。

In the first sample, there is only one graph, which is the given tree.

In the second samle, the given tree looks like this:

All possible graphs for the second sample are shown below, the minimum spanning tree is highlighted in red:

在第一个样例中，只存在一个图，即给定的树。

在第二个样例中，给定的树如下所示：

第二个样例中所有可能的图如下所示，其中最小生成树以红色高亮显示：