loj#P2779. 「BalticOI 2018」路径
「BalticOI 2018」路径
题目描述
题目译自 BalticOI 2018 Day2「Paths」
给定一张 个点 条边的无向图,每个点有一个颜色,所有点的颜色共有 种,编号为 。求图上有多少条长度至少为 的简单路径,满足路径上的每一个点的颜色互不相同。
路径上的点的连接顺序不同看作不同的两条路径。
输入格式
第一行包含三个整数 , 和 。
第二行包含 个在 到 之间的整数,表示每个点的颜色。
接下来的 行每行两个整数 和 ,表示图的一条边。
数据保证图无自环无重边。
输出格式
输出一个整数表示每一个点颜色都不同的路径条数。保证答案不会超过 。
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
数据范围与提示
子任务 | 分值 | 数据范围 |
---|---|---|
$1 \leqslant N,M \leqslant 100, 1 \leqslant K \leqslant 4$ | ||
$1 \leqslant N,M \leqslant 300\,000, 1 \leqslant K \leqslant 3$ | ||
$1 \leqslant N,M \leqslant 300\,000, 1 \leqslant K \leqslant 4$ | ||
$1 \leqslant N,M \leqslant 100\,000, 1 \leqslant K \leqslant 5$ |
请注意在 LibreOJ 上共有 个子任务,其中第一个子任务为样例。