Let ~p_v~ be the calculated price of each treehouse ~v~ ~(1 \le v \le N)~.

Notice that ~p_v~ has a bound of ~1 \le p_v \le N+1~. The maximum ~p_v~ can be constructed when each node is labeled with a distinct ID from ~1~ to ~N~. In this case ~p_1~ will be ~N+1~.

To find ~p_v~ efficiently, store a set for each treehouse which will consist of prices of all treehouses in its subtree. To merge the set of a treehouse and all its children, we can use Small-To-Large Merging.

Next, notice that if a treehouse ~u~ has a price of ~p_u~, its parent treehouse ~v~ will always have a price ~p_v~ such that ~p_v \ge p_u~. Therefore to calculate ~p_v~ for a treehouse ~v~, we loop from ~\max\{p_u\}~ (for all children treehouses ~u~) to ~N+1~ and check for the first positive integer not in the set of all prices.

Denote ~\text{ans}[X]~ to be the answer for some price ~X~ by only considering treehouses with ~p_v = X~.

Since a query refers to treehouses with prices greater than or equal to ~X~, we denote ~\text{suf}[X]~ to be the answer considering treehouses with price ~X \le p_v \le N+1~.

~\text{suf}[X]~ can be calculated in the following manner:

$$\displaystyle \text{suf}[X] = \min_{i=x}^{n+1} \text{ans}[i]$$

This is similar to running a suffix minimum by looping from ~N+1~ to ~1~. Note that ties should be broken by the treehouse with minimal ID, as mentioned in the problem statement. From here, we can answer queries for a certain ~X~ by outputting ~\text{suf}[X]~.

Time Complexity: ~\mathcal{O}(N \log N + Q)~