#P16901. [Ontak2026]山地旅行

[Ontak2026]山地旅行

题目描述

你的朋友 Klaudiusz 正准备进行一系列山地旅行。

山区中有 nn 个重要地点(山峰或山屋),编号为 1,2,…,n1,2,\ldots,n,并由 mm 条双向步道连接。地点 ii 的景观吸引力为 tit_i。

Klaudiusz 计划了 qq 次旅行。第 ii 次旅行从 aia_i 出发,到 bib_i 结束。

他不喜欢走回头路,因此旅行路线必须是一条简单路径:在同一次旅行中,任何地点都不能被访问超过一次。

一条路线的吸引力定义为该路线经过的所有地点(包括起点和终点)中最大的 tit_i。

对于每次询问,请求出从 aia_i 到 bib_i 的所有简单路径中,能够得到的最大可能吸引力。

输入格式

第一行包含三个整数 n,m,qn,m,q:

  • 2≤n≤1000002\le n\le100000;
  • 1≤m≤2000001\le m\le200000;
  • 1≤q≤1000001\le q\le100000。

第二行包含 nn 个整数 t1,t2,…,tnt_1,t_2,\ldots,t_n,其中:

1≤ti≤1091\le t_i\le10^9。

接下来 mm 行,每行包含两个整数 ui,viu_i,v_i,表示存在一条连接 uiu_i 与 viv_i 的双向步道。

保证:

  • 1≤ui,vi≤n1\le u_i,v_i\le n,ui≠viu_i\ne v_i;
  • 任意两个地点之间至多存在一条直接步道;
  • 整张图连通。

接下来 qq 行,每行包含两个整数 ai,bia_i,b_i,表示一次旅行的起点和终点,且 ai≠bia_i\ne b_i。

输出格式

输出 qq 行。第 ii 行输出第 ii 次旅行能够达到的最大可能吸引力。

样例

5 5 3
9 7 10 5 4
2 1
4 3
5 4
1 5
5 2
3 1
2 5
4 5
10
9
5

样例说明

  • 对于 3→13\to1,可走 3→4→5→13\to4\to5\to1,经过点的吸引力为 10,5,4,910,5,4,9,最大值为 1010。
  • 对于 2→52\to5,可走 2→1→52\to1\to5,得到最大值 99;直接走 2→52\to5 只能得到 77。
  • 对于 4→54\to5,唯一简单路径是直接边 4→54\to5,因此答案为 55。

子任务

子任务 限制 分值
1 n≤15,q≤15,m≤30n\le15,q\le15,m\le30 11
2 图是一条链:m=n−1,ui=i,vi=i+1m=n-1,u_i=i,v_i=i+1 7
3 图是一棵树:m=n−1m=n-1 13
4 n≤1500,m≤3500n\le1500,m\le3500 20
5 无额外限制 49