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

View as PDF

Submit solution


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

Author:
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 ith of which has a light with a brightness of ci. 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?

Constraints

For all subtasks:
1ci109
1ai,bi,ui,viN
uivi

Subtask 1 [10%]

2N,Q100

Subtask 2 [10%]

2N,Q3000

Subtask 3 [80%]

2N,Q50000

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, c1,c2,,cN.
The next N1 lines will contain two space-separated integers, ai and bi, indicating that there is an edge between nodes ai and bi.
The next Q lines will each contain two space-separated integers, ui and vi, indicating that your grandparents look at the path ui to vi.

Output Specification

Output Q lines. The ith line should contain a single integer: the similarity of the path from ui to vi.

Sample Input

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

Sample Output

Copy
1
2
1

Comments

There are no comments at the moment.