Odd Mineral Resource
Contest: Codeforces Round 700 (Div. 1)
Difficulty rating: 2900
Tags: binary search, bitmasks, brute force, data structures, probabilities, trees

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:

- mineral resource $$$c_i$$$ appears an odd number of times between city $$$u_i$$$ and city $$$v_i$$$; and
- $$$l_i \leq c_i \leq r_i$$$.

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.

Input format:
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.

Output format:
Print $$$q$$$ lines, the $$$i$$$-th of which contains an integer $$$c_i$$$ such that

- $$$c_i = {-1}$$$ if there is no such mineral resource that meets the required condition; or
- $$$c_i$$$ is the label of the chosen mineral resource of the $$$i$$$-th year. The chosen mineral resource $$$c_i$$$ should meet those conditions in the $$$i$$$-th year described above in the problem statement. If there are multiple choices of $$$c_i$$$, you can print any of them.

Constraints:
Time limit: 5.0 s
Memory limit: 1024.0 MB

Note:
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

- The first query is only to check whether mineral source $$$1$$$ appears an odd number of times between city $$$3$$$ and city $$$5$$$. The answer is no, because mineral source $$$1$$$ appears twice (an even number of times) between city $$$3$$$ and city $$$5$$$.
- The second and the third queries are the same but they can choose different mineral resources. Both mineral resources $$$2$$$ and $$$3$$$ are available.

Example input:
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

Example output:
-1
2
3
-1
3
2
2
3

Editorial:
Let $$$s(u, v, c)$$$ denote the number of cities between city $$$u$$$ and city $$$v$$$, whose mineral resource is $$$c$$$. We restate the problem that for each query $$$u, v, l, r$$$, find an integer $$$c$$$ such that $$$l \leq c \leq r$$$ and $$$s(u, v, c) \not\equiv 0 \pmod 2$$$.
We give a randomized algorithm with success probability extremely high. For every kind of mineral resources $$$1 \leq i \leq n$$$, we assign a random variable $$$X_i$$$ to it. Those random variables $$$X_i$$$ are independent and identically uniformly distributed from $$$[0, 2^{64}-1]$$$. For every city $$$u$$$, we assign its weight to be $$$X_{c_u}$$$.
For every query $$$u, v, l, r$$$, Let $$$f(u, v, l, r)$$$ be the bitwise XOR of all weights of all cities between city $$$u$$$ and city $$$v$$$, whose mineral resources are in $$$[l, r]$$$. We claim that
1. $$$ \Pr\left[\, f(u, v, l, r) = 0 \mid \forall c, s(u, v, c) \equiv 0 \pmod 2 \,\right] = 1$$$, which means that if a suitable $$$c$$$ does not exist then $$$f(u, v, l, r) = 0$$$ for certainty, and
2. $$$ \Pr\left[\, f(u, v, l, r) \neq 0 \mid \exists c, s(u, v, c) \not\equiv 0 \pmod 2 \,\right] = 1-2^{-64}$$$, which means that if a suitable $$$c$$$ does exist then $$$f(u, v, l, r) \neq 0$$$ with high probability.
1. $$$\Pr\left[\, \forall c, s(u, v, c) \equiv 0 \pmod 2 \mid f(u, v, l, r) = 0 \,\right] = 1-2^{-64}$$$, which implies with high probability no suitable mineral resource exists if $$$f(u, v, l, r) = 0$$$, and
2. $$$\Pr\left[\, \exists c, s(u, v, c) \not\equiv 0 \pmod 2 \mid f(u, v, l, r) \neq 0 \,\right] = 1$$$, which implies with certainty at least one suitable mineral resource exists.
1. to report no solution if $$$f(u, v, l, r) = 0$$$, and
2. to find a $$$c$$$ ($$$l \leq c \leq r$$$) such that $$$f(u, v, c, c) \neq 0$$$ if $$$f(u, v, l, r) \neq 0$$$.
Now consider there are $$$q$$$ queries. Let $$$A_i$$$ denote the event that the $$$i$$$-th query succeeds. The $$$i$$$-th query will succeed with probability $$$\Pr[A_i] \geq 1-2^{-64}$$$ (however, they may not be independent). Then we have $$$$$$ \begin{aligned} \Pr\left[ \bigwedge_{i=1}^{q} A_i \right] & = 1 - \Pr\left[ \bigvee_{i=1}^q \bar A_i \right] \\ & \geq 1 - \sum_{i=1}^q \Pr[\bar A_i] \\ & = 1 - \sum_{i=1}^q \left( 1 - \Pr[A_i] \right) \\ & \geq 1 - \sum_{i=1}^q \left( 1 - \left( 1 - 2^{-64} \right) \right) \\ & = 1 - 2^{-64}q, \end{aligned} $$$$$$ which means all queries succeed simultaneously with probability at least $$$1 - 2^{-64}q \geq 1-2^{-44}$$$ if $$$q \leq 2^{20}$$$, which is high enough under constraints of the problem.
To this end, we shall compute $$$f(u, v, l, r)$$$ and find a $$$c$$$ ($$$l \leq c \leq r$$$) such that $$$f(u, v, c, c) \neq 0$$$. This can be solved by consistent segment trees. Let's root the tree (by any vertex, say vertex $$$1$$$). For every vertex $$$u$$$, we maintain a (consistent) segment tree that for each interval $$$[l, r]$$$ computes $$$f(1, u, l, r)$$$. Let $$$\mathit{father}(u)$$$ be the father of vertex $$$u$$$, and $$$\mathit{lca}(u, v)$$$ be the least common ancestor of vertex $$$u$$$ and vertex $$$v$$$. Then $$$$$$ f(u, v, l, r) = f(1, u, l, r) \oplus f(1, v, l, r) \oplus f(1, \mathit{lca}(u, v), l, r) \oplus f(1, \mathit{father}(\mathit{lca}(u, v)), l, r). $$$$$$ For more details, please according to SPOJ COT. Therefore, we have solved this problem with high enough probability in $$$O(n \log n)$$$ time and space.