← 返回题目列表

AtCoder · abc399_g

G. 多彩的生成树

中文机器翻译题面 查看原题

分数: 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