loj#P2779. 「BalticOI 2018」路径

「BalticOI 2018」路径

题目描述

题目译自 BalticOI 2018 Day2「Paths

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

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

输入格式

第一行包含三个整数 NN, MMKK

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

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

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

输出格式

输出一个整数表示每一个点颜色都不同的路径条数。保证答案不会超过 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 个子任务,其中第一个子任务为样例。