「BalticOI 2018」路径
题目描述
给定一个 个点 条边的无向图，每个点有 中的一种颜色。求图上有多少条长度至少为 2 的简单路径，满足路径上每个点的颜色互不相同。
路径的连接顺序不同视为不同路径。
输入格式
第一行：（点数、边数、颜色数）
第二行： 个整数，表示每个点的颜色（）
接下来 行：每行两个整数 ，表示一条边
数据保证图无自环无重边。
输出格式
一个整数，表示满足条件的路径条数（保证不超过 ）
样例 1
输入
4 3 3
1 2 1 3
1 2
2 3
4 2
输出
10
解释：满足条件的路径有 10 条，包括单边路径（长度 2）和部分长度为 3 的路径。
样例 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
输出
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$ |