|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|3 초||1024 MB||91||35||26||38.235%|
In the backyard of Seoul Science High School, there is a magical tree with $N$ vertices, where every vertex contains a single fruit. (A tree is a connected undirected graph with $N-1$ edges.)
Although it is prohibited to pick any fruits from the tree, students naturally want to secretly pick some fruit to eat. To prevent being caught by the teacher, they use the following procedure to choose a fruit to pick:
Of course, they are very nice students, so they never actually pick any of the fruits. They simply think of it. :)
Being exceptionally nice students, they naturally extended their thought experiment as a query problem. Thus, given $Q$ independent queries, you should find the answer or state that no majority exists. Can you solve it?
The first line contains two integers $N, Q$. ($1 \le N, Q \le 250 000$).
In the next line, $N$ integers $c_i$ is given, denoting the type of fruit in vertex $i$. ($1 \le c_i \le N$).
In the next $N-1$ lines, two integers $a_i, b_i$ denoting endpoints of each edge are given. ($1 \le a_i, b_i \le N, a_i \neq b_i$).
In the next $Q$ lines, two integers $s_i, e_i$ denoting two endpoints of each path are given. ($1 \le s_i, e_i \le N$).
Print $Q$ lines. For each line, print a single integer denoting the type of fruit that forms a majority in a given path. If there exists no majority in the given path, print $-1$.
7 4 3 1 1 2 1 1 2 1 3 7 5 2 3 5 3 5 6 4 5 1 4 7 2 3 3 4 7
-1 1 1 2
Contest > Open Cup > 2018/2019 Season > Stage 19: Grand Prix of Daejeon F번