题目详情 - 「BalticOI 2018」路径

ID: 834

传统题

3000ms

1024MiB

难度: (无)

上传者:

标签>

2018

BalticOI

题目描述

题目译自 BalticOI 2018 Day2「Paths」

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

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

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

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

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

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

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

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

子任务	分值	数据范围
$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$ 个子任务，其中第一个子任务为样例。