AtCoder Beginner Contest 335

Non-Decreasing Colorful Path

题目

输入有 \(n\) 个顶点和 \(m\) 条边的连通的无向图（没有重边和自环），每个顶点上有一个整数 \(A_{i}\)，输出所有从顶点 \(1\) 到 \(N\) 的简单路径的最高得分。如果路径中顶点上的整数构成的序列非递减，那么该路径的得分为序列中不同整数的个数，否则得分为 \(0\)。

数据范围：\(2\leq n\leq 2 \times 10^{5}\)，\(1\leq A_{i}\leq 2\times 10^{5}\)。

思路

虽然是无向图，但是序列需要非递减才能有得分。进一步观察可以发现，对于一条非递减路径，所有包含相同整数的顶点只会贡献 \(1\) 个得分，我们可以将这些顶点缩为一个顶点。所以，只需要建立满足递增条件的有向边，如果边的两个顶点包含相同的整数，则使用并查集将它们连接（缩点）。然后问题就变为求 DAG 中两个顶点之间的最长路径，不过和一般的使用拓扑排序 + 动态规划来求解的方式不同，因为缩点的缘故，该题不是很好使用拓扑排序。由于 \(A_{i}\) 的范围比较小，从小到大枚举顶点整数，然后扩展以该整数为起点的边，结合动态规划可以比较方便的求出答案。实现时，需要注意起点和终点同样可能被缩点，使用时将其替换为并查集中所在连通块的根节点。