AT_abc335_e [ABC335E] Non-Decreasing Colorful Path

题目描述

给定一个有 $N$ 个顶点、$M$ 条边的连通无向图，第 $i$ 条边连接顶点 $U_i$ 和顶点 $V_i$（双向）。
此外，每个顶点上都写有一个整数，顶点 $v$ 上写着整数 $A_v$。

对于从顶点 $1$ 到顶点 $N$ 的所有简单路径（即不重复经过同一顶点的路径），定义如下得分方式：

• 将路径上经过的顶点所写的整数，按经过顺序排列成一个数列 $S$。
• 如果 $S$ 不是广义单调递增的，则该路径的得分为 $0$。
• 否则，$S$ 中包含的不同整数的个数即为该路径的得分。

请在所有从顶点 $1$ 到顶点 $N$ 的简单路径中，输出得分最高的路径的得分。

什么是广义单调递增？长度为 $l$ 的数列 $S=(S_1,S_2,\dots,S_l)$ 被称为广义单调递增，当且仅当对于所有整数 $1 \le i < l$，都有 $S_i \le S_{i+1}$。

输入格式

输入按以下格式从标准输入读入。

$N$ $M$
$A_1$ $A_2$ $\dots$ $A_N$
$U_1$ $V_1$
$U_2$ $V_2$
$\vdots$
$U_M$ $V_M$

输出格式

请输出一个整数，表示最大得分。

输入输出样例 #1

输入 #1

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

输出 #1

4

输入输出样例 #2

输入 #2

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

输出 #2

0

输入输出样例 #3

输入 #3

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

输出 #3

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

对于路径 $1 \rightarrow 3 \rightarrow 4 \rightarrow 5$，$S=(10,30,40,50)$，该路径的得分为 $4$，这是最大得分。

样例解释 2

不存在从顶点 $1$ 到顶点 $N$ 的简单路径使得 $S$ 是广义单调递增的。这种情况下，最大得分为 $0$。

由 ChatGPT 4.1 翻译