A14161. Odd Mineral Resource
编程题
普及/提高-
知识点
题目描述
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.
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.
输入格式
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.
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
- $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.
- $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.
输入输出样例
输入 #1
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
-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
- 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.
- 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.