当前没有测试数据。

Ex - 给加权图上色

得分: $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$

输出

输出回答。

3 2 1
1 2 1
2 3 2

6

比如，一个 $(v,x)=(2,1)$ 的操作会把顶点 $1,2$ 点染成红色，一个 $(v,x)=(1,0)$ 的操作会把顶点 $1$ 染成红色。

在最多一个操作之后，被染成红色的顶点的集合可以是以下六种之一: $\{\},\{1\},\{2\},\{3\},\{1,2\},\{1,2,3\}$。

5 0 2

16

给定的图可能是非连通的。

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

40

给定的图可能有重边和自环。