分数: 675 点
问题陈述
给你一个连通的无向图 N 顶点和 M 边,其中顶点被标记 1 to N。该图不包含自环,但可能包含多边。每条边都有一种颜色,并且 i第一条边有颜色 c_i (1 \leq c_i \leq C) 并连接顶点 u_i 和 v_i。另外,还有一个序列 给出了 A = (A_1, A_2, \dots, A_C) 。
该图的生成树中,满足以下条件的称为 多彩的跨越树:
- 对于每个整数 i 这样 1 \leq i \leq C,颜色的边数 生成树中最多包含 i 生成树中最多包含 A_i.
查找整数对的数量 (L, R) 与 1 \leq L \leq R \leq C 满足以下条件:
- 存在一棵彩色生成树 T 使得每条边 T 有颜色 c 与 L \leq c \leq 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
- If i \neq j,那么 (u_i, v_i, c_i) \neq (u_j, v_j, c_j)
- 给定的图形已连接。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
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) 与 1 \leq L \leq R \leq C 满足问题陈述中的条件。
示例输入 1
3 4 3 1 2 1 1 2 1 1 2 2 1 3 3 2 3 2
示例输出 1
4
例如, (L, R) = (1, 2) 满足条件,因为生成树 T 由第 1 条和第 4 条边组成的是一棵彩色生成树,并且所有边都在 T 有颜色 c 与 1 \leq c \leq 2.
有四对 (L, R) 满足条件: (1, 2), (1, 3), (2, 2), (2, 3).
示例输入 2
5 10 6 2 2 4 1 1 1 1 3 2 1 5 4 2 3 3 1 4 1 4 5 1 4 5 3 2 4 1 1 4 3 1 3 4 1 2 5
示例输出 2
11
示例输入 3
10 20 5 2 4 4 6 4 5 9 1 4 5 2 2 8 5 8 9 4 1 10 5 8 10 1 8 9 5 4 8 2 4 10 4 5 8 3 5 9 5 6 10 2 3 5 4 4 6 1 3 4 3 7 9 3 5 7 1 1 3 3 1 8 5 5 10 4
示例输出 3
2