Monkey Motel

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 2.0s
Java 3.0s
Python 3.0s
Memory limit: 256M
Java 512M
Python 512M

Problem type

William, the monkey, is an investor currently checking out the AAC Motel, an oak tree home to N treehouses each labeled with an ID from 1 to N, connected by N-1 bi-directional branches. Furthermore, each treehouse has a room size of a_i and William sets the treehouse with ID 1 to be the root of the whole motel.

We define the price of a treehouse r to be the smallest positive integer that is not present as a room size among all treehouses in the subtree rooted at r.

Over the next Q days of his visit, he will provide the owner with a value X_i, and among all treehouses with price greater than or equal to X_i, the owner must reply with the ID of the treehouse with the minimum sized subtree. If there are multiple treehouses satisfying the conditions, William asks for the treehouse with the minimum ID. On the other hand, if there are no treehouses that satisfy a query, the owner must reply with -1.

Help the owner answer William's queries to avoid eviction!


1 \le N, Q \le 3 \times 10^5

1 \le a_i, X_i \le 10^9

1 \le u, v \le N

Subtask 1 [10%]

1 \le N, Q \le 5 \times 10^3

Subtask 2 [90%]

No additional constraints.

Input Specification

The first line of input contains two space-separated integers, N and Q representing the number of treehouses and queries, respectively.

The second line of input contains N space-separated integers a_i.

The next N-1 lines each contain 2 integers u and v representing a branch between two treehouses.

The final Q lines will each contain a single integer X_i.

Output Specification

Output Q lines, each with the answer for the i^\text{th} query. If there are no treehouses satisfying the conditions, output -1.

Sample Input

6 2
5 1 3 2 4 6
1 2
2 3
2 6
1 4
4 5

Sample Output


Sample Explanation

Consider the depicted tree below, with the black text inside each treehouse being the ID, the red text above being the room size, and the blue text below being the price.

For the first query, the only treehouse with price \ge 4 is 1.

For the second query, there are no treehouses with price \ge 13 so -1 is the answer.


There are no comments at the moment.