AT_abc399_g [ABC399G] Colorful Spanning Tree

[problemUrl]: https://atcoder.jp/contests/abc399/tasks/abc399_g 给定一个包含 $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 完成