#P5891. 「BalticOI 2018」路径

「BalticOI 2018」路径

题目描述

题目译自 BalticOI 2018 Day2「Paths」

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

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

输入格式

第一行包含三个整数 NN, MM 和 KK。

第二行包含 NN 个在 11 到 KK 之间的整数,表示每个点的颜色。

接下来的 MM 行每行两个整数 aa 和 bb,表示图的一条边。

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

输出格式

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

4 3 3
1 2 1 3
1 2
2 3
4 2
10
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
70

数据范围与提示

子任务 分值 数据范围
11 2323 $1 \leqslant N,M \leqslant 100, 1 \leqslant K \leqslant 4$
22 2020 $1 \leqslant N,M \leqslant 300\,000, 1 \leqslant K \leqslant 3$
33 2727 $1 \leqslant N,M \leqslant 300\,000, 1 \leqslant K \leqslant 4$
44 3030 $1 \leqslant N,M \leqslant 100\,000, 1 \leqslant K \leqslant 5$

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