P12180 DerrickLo's City (UBC002C)

DerrickLo 看到了一个 $n \le 7.5 \times 10^5$ 的题，并且发现很多人写了 $O(n^2)$ 过了。于是他想写 $O(n\log^3n)$，但是挂了。于是将原题的序列改成了树。 注：以上故事是将出题人的名字换成 DerrickLo 得到的。

In a game, DerrickLo is operating a city. There are $n$ groups in this city. Since the relations between these groups are not very nice, DerrickLo needs to hold some meetings to relieve the relationships. The city is constructed of $n$ towns indexed from $1$ to $n$. There is exactly one group in each town. The group in town $i$ is indexed $i$. The towns are linked with $n - 1$ roads, so that every two towns can get to each other through these roads. Every time DerrickLo holds a meeting, he will invite all the groups whose index is in an interval $[l, r]$ to a town $p$, where town $p$ is the place of the meeting. Since the relations are not very nice, groups can not pass by a town whose group is also attending the meeting while going to town $p$. Because DerrickLo is new to this game, the task of determining town $p$ is handed to you.

The first line contains two positive integers $n, q(1 \le n, q \le 10^5)$, the number of towns and the number of meetings. There are two positive integers $a_i, b_i$ in the next $n - 1$ lines, describing an edge which directly links town $a_i$ and $b_i$. It's guaranteed that these roads forms a tree. There are two positive integers $l_i, r_i(1 \le l_i \le r_i \le n)$ in the next $q$ lines, which means that DerrickLo invites the groups indexed in $[l_i, r_i]$ to a meeting.

For every meeting, if there exists such town $p$, output `Yes`. Otherwise output `No`.

For the first meeting, the place of the meeting can be town $1$, $2$ or $6$. For the second meeting, it can be proved that no matter which town is chosen, one of group $2, 4$ will pass by the other's town.