Codeforces Round 700 (Div. 1) |
---|
Finished |
In Homer's country, there are $$$n$$$ cities numbered $$$1$$$ to $$$n$$$ and they form a tree. That is, there are $$$(n-1)$$$ undirected roads between these $$$n$$$ cities and every two cities can reach each other through these roads.
Homer's country is an industrial country, and each of the $$$n$$$ cities in it contains some mineral resource. The mineral resource of city $$$i$$$ is labeled $$$a_i$$$.
Homer is given the plans of the country in the following $$$q$$$ years. The plan of the $$$i$$$-th year is described by four parameters $$$u_i, v_i, l_i$$$ and $$$r_i$$$, and he is asked to find any mineral resource $$$c_i$$$ such that the following two conditions hold:
As the best friend of Homer, he asks you for help. For every plan, find any such mineral resource $$$c_i$$$, or tell him that there doesn't exist one.
The first line contains two integers $$$n$$$ ($$$1 \leq n \leq 3 \cdot 10^5$$$) and $$$q$$$ ($$$1 \leq q \leq 3 \cdot 10^5$$$), indicating the number of cities and the number of plans.
The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq n$$$).
Then the $$$i$$$-th line of the following $$$(n-1)$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \leq x_i, y_i \leq n$$$) with $$$x_i \neq y_i$$$, indicating that there is a bidirectional road between city $$$x_i$$$ and city $$$y_i$$$. It is guaranteed that the given roads form a tree.
Then the $$$i$$$-th line of the following $$$q$$$ lines contains four integers $$$u_i$$$, $$$v_i$$$, $$$l_i$$$, $$$r_i$$$ ($$$1 \leq u_i \leq n$$$, $$$1 \leq v_i \leq n$$$, $$$1 \leq l_i \leq r_i \leq n$$$), indicating the plan of the $$$i$$$-th year.
Print $$$q$$$ lines, the $$$i$$$-th of which contains an integer $$$c_i$$$ such that
6 8 3 2 1 3 1 3 1 2 1 3 2 4 2 5 4 6 3 5 1 1 3 5 1 3 3 5 1 3 1 1 2 2 1 1 3 3 1 4 1 5 1 6 1 3 1 6 1 3
-1 2 3 -1 3 2 2 3
In the first three queries, there are four cities between city $$$3$$$ and city $$$5$$$, which are city $$$1$$$, city $$$2$$$, city $$$3$$$ and city $$$5$$$. The mineral resources appear in them are mineral resources $$$1$$$ (appears in city $$$3$$$ and city $$$5$$$), $$$2$$$ (appears in city $$$2$$$) and $$$3$$$ (appears in city $$$1$$$). It is noted that
Name |
---|