/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
N 頂点 M 辺の無向グラフが与えられます。i 番目の辺は頂点 A_i と B_i を結び、重みは C_i です。
最初、全ての頂点は黒く塗られています。あなたは、次の操作を高々 K 回行うことができます。
- 操作：頂点 v と整数 x を自由に選ぶ。頂点 v から重み x 以下の辺のみを通って到達可能な頂点全て(v 自身を含む)を赤く塗る
操作後に赤く塗られている頂点の集合として考えられるものは何通りありますか？
998244353 で割ったあまりを求めてください。
制約
- 2 \leq N \leq 10^5
- 0 \leq M \leq 10^5
- 1 \leq K \leq 500
- 1 \leq A_i,B_i \leq N
- 1 \leq C_i \leq 10^9
- 入力に含まれる値は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N M K A_1 B_1 C_1 \vdots A_M B_M C_M
出力
答えを出力せよ。
入力例 1
3 2 1 1 2 1 2 3 2
出力例 1
6
例えば (v,x)=(2,1) と選んで操作を行うと、頂点 1,2 を赤く塗ることができ、(v,x)=(1,0) と選んで操作を行うと、頂点 1 を赤く塗ることができます。
高々 1 回の操作の後で赤く塗られている頂点の集合としてあり得るものは \{\},\{1\},\{2\},\{3\},\{1,2\},\{1,2,3\} の 6 つです。
入力例 2
5 0 2
出力例 2
16
与えられるグラフは連結とは限りません。
入力例 3
6 8 2 1 2 1 2 3 2 3 4 3 4 5 1 5 6 2 6 1 3 1 2 10 1 1 100
出力例 3
40
与えられるグラフは多重辺や自己ループを持つかもしれません。
Score : 600 points
Problem Statement
Given is an undirected graph with N vertices and M edges. The i-th edge connects Vertices A_i and B_i and has a weight of C_i.
Initially, all vertices are painted black. You can do the following operation at most K times.
- Operation: choose any vertex v and any integer x. Paint red all vertices reachable from the vertex v by traversing edges whose weights are at most x, including v itself.
How many sets can be the set of vertices painted red after the operations?
Find the count modulo 998244353.
Constraints
- 2 \leq N \leq 10^5
- 0 \leq M \leq 10^5
- 1 \leq K \leq 500
- 1 \leq A_i,B_i \leq N
- 1 \leq C_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M K A_1 B_1 C_1 \vdots A_M B_M C_M
Output
Print the answer.
Sample Input 1
3 2 1 1 2 1 2 3 2
Sample Output 1
6
For example, an operation with (v,x)=(2,1) paints Vertices 1,2 red, and an operation with (v,x)=(1,0) paints Vertex 1.
After at most one operation, the set of vertices painted red can be one of the following six: \{\},\{1\},\{2\},\{3\},\{1,2\},\{1,2,3\}.
Sample Input 2
5 0 2
Sample Output 2
16
The given graph may not be connected.
Sample Input 3
6 8 2 1 2 1 2 3 2 3 4 3 4 5 1 5 6 2 6 1 3 1 2 10 1 1 100
Sample Output 3
40
The given graph may have multi-edges and self-loops.