G - Colorful Spanning Tree Editorial /

Time Limit: 6 sec / Memory Limit: 1024 MiB

配点 : 675 点

問題文

頂点に 1 から N の番号がついた N 頂点 M 辺の連結無向グラフが与えられます。グラフは自己ループを含みませんが、多重辺を含む可能性があります。辺には色がついていて、i 番目の辺は頂点 u_i と頂点 v_i を結ぶ色 c_i (1 \leq c_i \leq 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 を満たすようなものが存在する。

制約

  • 2 \leq N \leq 150
  • N - 1 \leq M \leq \min\left(\frac{CN(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 \lt 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)
  • 入力で与えられるグラフは連結
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

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

出力

1 \leq L \leq R \leq C を満たす整数の組 (L, R) のうち問題文の条件を満たすものの個数を出力せよ。

入力例 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) は問題文の条件を満たします。これは 1 番目の辺と 4 番目の辺からなる全域木 T はカラフル全域木で、かつ T に含まれる任意の辺の色が L 以上 R 以下であるからです。
問題文の条件を満たす (L, R) は (1, 2), (1, 3), (2, 2), (2, 3) の 4 個です。

入力例 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

Score : 675 points

Problem Statement

You are given a connected undirected graph with N vertices and M edges, where the vertices are labeled 1 to N. The graph does not contain self-loops, but it may contain multi-edges. Each edge has a color, and the i-th edge has a color c_i (1 \leq c_i \leq C) and connects vertices u_i and v_i. Also, a sequence A = (A_1, A_2, \dots, A_C) is given.

Among the spanning trees of this graph, those satisfying the following condition are called colorful spanning trees:

  • For every integer i such that 1 \leq i \leq C, the number of edges of color i included in the spanning tree is at most A_i.

Find the number of integer pairs (L, R) with 1 \leq L \leq R \leq C that satisfy the following condition:

  • There exists a colorful spanning tree T such that every edge in T has a color c with L \leq c \leq R.

Constraints

  • 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, then (u_i, v_i, c_i) \neq (u_j, v_j, c_j)
  • The given graph is connected.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print the number of integer pairs (L, R) with 1 \leq L \leq R \leq C that satisfy the condition in the problem statement.

Sample Input 1

3 4 3
1 2 1
1 2 1
1 2 2
1 3 3
2 3 2

Sample Output 1

4

For example, (L, R) = (1, 2) satisfies the condition, because the spanning tree T formed by the 1st and 4th edges is a colorful spanning tree, and all edges in T have colors c with 1 \leq c \leq 2.
There are four pairs (L, R) that satisfy the condition: (1, 2), (1, 3), (2, 2), (2, 3).

Sample Input 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

Sample Output 2

11

Sample Input 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

Sample Output 3

2