New Year's '18 P6 - Old Christmas Lights II

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 4.5s
Memory limit: 256M

Problem types

Your grandparents have decided to come visit you for Christmas! However, you notice that they are squinting as they look at your Christmas tree!

Being the computer science nerd that you are, your Christmas tree is a tree with N nodes, the i^\text{th} of which has a light with a brightness of c_i. The similarity of a path is the minimum non-negative difference between the brightnesses of any two distinct nodes on the path. Given that your grandparents look at Q paths, can you tell them what the similarity of each path is?


For all subtasks:
1 \le c_i \le 10^9
1 \le a_i,b_i,u_i,v_i \le N
u_i \ne v_i

Subtask 1 [10%]

2 \le N, Q \le 100

Subtask 2 [10%]

2 \le N, Q \le 3\,000

Subtask 3 [80%]

2 \le N, Q \le 50\,000

Input Specification

The first line of input will contain two space-separated integers, N and Q.
The next line of input will contain N space-separated integers, c_1, c_2, \dots, c_N.
The next N-1 lines will contain two space-separated integers, a_i and b_i, indicating that there is an edge between nodes a_i and b_i.
The next Q lines will each contain two space-separated integers, u_i and v_i, indicating that your grandparents look at the path u_i to v_i.

Output Specification

Output Q lines. The i^\text{th} line should contain a single integer: the similarity of the path from u_i to v_i.

Sample Input

5 3
1 8 7 5 6
2 4
4 1
3 1
1 5
2 3
4 3
5 2

Sample Output



There are no comments at the moment.