多彩路径计数(Paths)

题目描述

本题对应 BalticOI 2018 Day 2 Problem C：Paths。

给定一张包含 $n$ 个顶点、$m$ 条无向边的无向图，每个顶点都被染上了 $1 \sim k$ 中的一种颜色。

请你统计图中有多少条包含至少 $2$ 个顶点的路径，使得路径上所有顶点的颜色互不相同。

注意：路径是有方向的，即顶点序列 $(u_1, u_2, \dots, u_t)$ 与其反转 $(u_t, \dots, u_2, u_1)$ 视为两条不同的路径。

输入格式

第一行包含三个正整数 $n, m, k$，分别表示顶点数、边数与颜色种数。

第二行包含 $n$ 个正整数 $c_1, c_2, \dots, c_n$（$1 \le c_i \le k$），表示每个顶点的颜色。

接下来 $m$ 行，每行包含两个正整数 $u, v$，表示一条连接顶点 $u$ 和 $v$ 的无向边。

输出格式

输出一行一个整数，表示满足条件的路径总数。

样例输入 #1

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

样例输出 #1

10

样例输入 #2

9 11 4
1 2 3 4 1 2 1 2 2
1 2
1 3
2 3
2 4
3 6
6 2
6 5
4 3
4 5
7 8
9 8

样例输出 #2

70

数据范围

对于 $100\%$ 的数据，$1 \le n, m \le 3 \times 10^5$，$1 \le k \le 5$。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1600。

测试点分布

出处：原题链接