Non-Decreasing Colorful Path

题目描述

有一个连通的无向图，包含 $N$ 个顶点和 $M$ 条边，第 $i$ 条边双向连接顶点 $U_i$ 与顶点 $V_i$。
每个顶点上都写着一个整数，顶点 $v$ 上写着整数 $A_v$。 对于从顶点 $1$ 到顶点 $N$ 的一条简单路径（即不经过同一顶点多次的路径），分数按如下方式确定：

设沿路径访问的顶点上写着的整数序列为 $S$，按访问顺序列出。 如果 $S$ 不是非递减的，则该路径的分数为 $0$。 否则，分数为 $S$ 中不同整数的个数。

在所有从顶点 $1$ 到顶点 $N$ 的简单路径中，找出分数最高的路径并输出该分数。

输入格式

输入从标准输入给出，格式如下： $N$ $M$ $A_1$ $A_2$ $\dots$ $A_N$ $U_1$ $V_1$ $U_2$ $V_2$ $\vdots$ $U_M$ $V_M$

输出格式

输出一个整数，表示答案。

5 6
10 20 30 40 50
1 2
1 3
2 5
3 4
3 5
4 5

4

4 5
1 10 11 4
1 2
1 3
2 3
2 4
3 4

0

10 12
1 2 3 3 4 4 4 6 5 7
1 3
2 9
3 4
5 6
1 2
8 9
4 5
8 10
7 10
4 6
2 8
6 7

5

提示

所有输入值均为整数。 $2 \le N \le 2 \times 10^5$ $N-1 \le M \le 2 \times 10^5$ $1 \le A_i \le 2 \times 10^5$ 图是连通的。 1 \le U_i < V_i \le N 若 $i \neq j$ 则 $(U_i,V_i) \neq (U_j,V_j)$。路径 $1 \rightarrow 3 \rightarrow 4 \rightarrow 5$ 的 $S=(10,30,40,50)$，分数为 $4$，这是最大值。
在这种情况下不存在从顶点 $1$ 到顶点 $N$ 的简单路径使得 $S$ 为非递减序列，则最大分数为 $0$。

标签: AtCoder|abc335E

来源

AtCoder|abc335E