#2779. 「BalticOI 2018」路径

内存限制:1024 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Mingqi_H

题目描述

题目译自 BalticOI 2018 Day2「Paths

给定一张 N 个点 M 条边的无向图,每个点有一个颜色,所有点的颜色共有 K 种,编号为 1\ldots K 。求图上有多少条长度至少为 2 的简单路径,满足路径上的每一个点的颜色互不相同。

路径上的点的连接顺序不同看作不同的两条路径。

输入格式

第一行包含三个整数 N , M K

第二行包含 N 个在 1 K 之间的整数,表示每个点的颜色。

接下来的 M 行每行两个整数 a b ,表示图的一条边。

数据保证图无自环无重边。

输出格式

输出一个整数表示每一个点颜色都不同的路径条数。保证答案不会超过 10^{18}

样例

样例 1 输入

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

样例 1 输出

10

样例 1 解释

样例 1 中表达的图如上图所示。每个点的底色分别为白色(颜色 1 )、灰色(颜色 2 )或黑色(颜色 3 )。共有 10 条路径满足路径上的所有点的颜色都不同。它们是:1-2, 2-1, 2-3, 3-2, 2-4, 4-2, 1-2-4, 4-2-1, 3-2-44-2-3

注意 1 不能看作是一条路径,因为一条路径至少连接两个点。1-2-3 也不满足条件,因为有两个点都是 1 号颜色。

样例 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

数据范围与提示

子任务 分值 数据范围
1 23 1 \leqslant N,M \leqslant 100, 1 \leqslant K \leqslant 4
2 20 1 \leqslant N,M \leqslant 300\,000, 1 \leqslant K \leqslant 3
3 27 1 \leqslant N,M \leqslant 300\,000, 1 \leqslant K \leqslant 4
4 30 1 \leqslant N,M \leqslant 100\,000, 1 \leqslant K \leqslant 5

请注意在 LibreOJ 上共有 5 个子任务,其中第一个子任务为样例。