分数: 525 点
问题陈述
有一个连通无向图 N 顶点和 M 边缘,其中 i第一条边连接顶点 U_i 和顶点 V_i 双向。
每个顶点上面都写有一个整数,整数 A_v 写在顶点上 v.
对于从顶点开始的简单路径 1 到顶点 N (不多次经过同一顶点的路径),分数确定如下:
- 让 S 是沿路径写在顶点上的整数序列,按访问顺序列出。
- If S 不是非递减的,该路径的分数是 0.
- 否则,分数是不同整数的数量 S.
查找从顶点开始的路径 1 到顶点 N 在所有简单路径中得分最高并打印该得分。
这意味着什么 S 非递减?
一个序列 S=(S_1,S_2,\dots,S_l) 长度 l 被认为是非递减的当且仅当 S_i \le S_{i+1} 对于所有整数 1 \le i < l.约束
- 所有输入值均为整数。
- 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
- (U_i,V_i) \neq (U_j,V_j) if i \neq j.
输入
输入由标准输入按以下格式给出:
N M A_1 A_2 \dots A_N U_1 V_1 U_2 V_2 \vdots U_M V_M
输出
将答案打印为整数。
示例输入 1
5 6 10 20 30 40 50 1 2 1 3 2 5 3 4 3 5 4 5
示例输出 1
4
路径 1 \rightarrow 3 \rightarrow 4 \rightarrow 5 有 S=(10,30,40,50) 得分为 4,这是最大值。
示例输入 2
4 5 1 10 11 4 1 2 1 3 2 3 2 4 3 4
示例输出 2
0
没有从顶点开始的简单路径 1 到顶点 N 这样 S 不减少。在这种情况下,最高分数是 0.
示例输入 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