g7-07682. 路径上的最大值 未做

给定一棵有 $n$ 个结点的无向树，结点编号为 $1\sim n$，第 $i$ 个结点有一个正整数点权 $w_i$。

树中两个结点 $u$ 与 $v$ 之间的路径，指的是连接 $u$ 与 $v$ 的简单路径，路径包含 $u$ 和 $v$ 本身。

现在有 $q$ 次询问，每次询问给出两个结点 $u,v$，请你求出 $u$ 到 $v$ 的路径上所有结点的最大点权。

第一行一个正整数 $n$，表示树的结点数。

第二行 $n$ 个正整数 $w_1,w_2,\dots ,w_n$，依次表示每个结点的点权。

接下来 $n-1$ 行，每行两个正整数 $u,v$，表示结点 $u$ 与结点 $v$ 之间有一条边；当 $n=1$ 时没有边。

接下来一行一个正整数 $q$，表示询问次数。

接下来 $q$ 行，每行两个正整数 $u,v$，表示一次询问。

共 $q$ 行，每行一个整数，依次表示每次询问路径上的最大点权。

输入：

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

输出：

7
9
5

样例说明：

• 询问 $4,5$：路径为 $4-2-5$，点权依次为 $1,3,7$，最大值为 $7$；
• 询问 $3,4$：路径为 $3-1-2-4$，点权依次为 $9,5,3,1$，最大值为 $9$；
• 询问 $1,1$：路径只包含结点 $1$，最大值为 $w_1=5$。

• $1\le n\le 1000$，$1\le q\le 1000$；
• $1\le w_i\le 10000$；
• $1\le u,v\le n$，保证输入的 $n-1$ 条边恰好构成一棵树。