AT_abc399_g.[ABC399G] Colorful Spanning Tree

给定一个包含 $N$ 个顶点和 $M$ 条边的连通无向图，顶点编号为 $1$ 到 $N$。图中不含自环，但可能包含重边。每条边有颜色，第 $i$ 条边连接顶点 $u_i$ 和 $v_i$，颜色为 $c_i$（$1 \leq c_i \leq C$）。此外给定一个长度为 $C$ 的整数序列 $A = (A_1, A_2, \dots, A_C)$。

定义该图的 彩色生成树 为满足以下条件的生成树：

• 对于所有满足 $1 \leq i \leq C$ 的整数 $i$，生成树中包含的颜色为 $i$ 的边数不超过 $A_i$ 条。

请计算满足 $1 \leq L \leq R \leq C$ 的整数对 $(L, R)$ 中符合以下条件的个数：

• 存在一个彩色生成树 $T$，使得 $T$ 中每条边的颜色 $c$ 均满足 $L \leq c \leq R$。

输入通过标准输入给出，格式如下：

$N$ $M$ $C$
$A_1$ $A_2$ $\dots$ $A_C$
$u_1$ $v_1$ $c_1$
$u_2$ $v_2$ $c_2$
$\vdots$
$u_M$ $v_M$ $c_M$

输出满足条件的整数对 $(L, R)$ 的个数。

约束条件

• $2 \leq N \leq 150$
• $N - 1 \leq M \leq \min\left( \frac{C N (N - 1)}{2}, 5 \times 10^5 \right)$
• $1 \leq C \leq 300$
• $1 \leq A_i \leq N - 1$
• $\sum_{i=1}^C A_i \leq 300$
• $1 \leq u_i < v_i \leq N$
• $1 \leq c_i \leq C$
• 若 $i \neq j$，则 $(u_i, v_i, c_i) \neq (u_j, v_j, c_j)$
• 输入保证图是连通的
• 输入的所有值均为整数

样例解释 1

例如，$(L, R) = (1, 2)$ 满足条件。因为由第 $1$ 条边和第 $4$ 条边构成的生成树 $T$ 是彩色生成树，且 $T$ 中所有边的颜色均在 $L$ 到 $R$ 范围内。符合条件的 $(L, R)$ 共有 $4$ 个：$(1, 2)$、$(1, 3)$、$(2, 2)$、$(2, 3)$。

翻译由 DeepSeek R1 完成