PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: DOlaBMOon
Tester: Hussain
Editorialist: Taranpreet Singh
DIFFICULTY:
EasyMedium
PREREQUISITES:
DFS or BFS, DP on trees and Binary Lifting.
PROBLEM:
Given a Tree rooted at one, each node having an integer value A[i] associated with it, we need to answer following query.
 Given a vertex V and a value W, Find Number of times we get the next greater element when W is first element, and we move from root 1 to V.
SUPER QUICK EXPLANATION

Preprocess answer for $W = 0$ for all nodes, say ans array and for every query use binary lifting to reach the node farthest from root on path of root to $V$ such that maximum value on path from root to this node is less than or equal to $W$, say node $X$. Answer is Just $ans[V]ans[X]$.
EXPLANATION
First of all, let’s solve this problem without queries, that is, Calculate answer for W = 0 for all nodes.
Suppose we have two values for each node, say MX[i] and C[i]  Maximum value from root to node, and Number of times Chef learnt a new dish, that is, number of times the maximum value changes on path from root to node.
Give a try to formulating a recurrence for calculating these two values for a node, when these values for parent are known. Cannot figure out? Refer the secret box
Click to view
If Max value up to parent node is less than value associated with current node, then Count for current node is one more than count up to parent, and Maximum value is value associated with current node. Otherwise Maximum value doesn’t change, so count too doesn’t change, thus, is same as parent.
Also, for root 1, MX[1] = A[1] and C[1] = 1
So, now we have solved this problems for all nodes and W = 0.
But about our actual problem?? For that, we need another observation regarding maximum values MX.
Lemma: As we move down from parent to child, the maximum value either remain same or increases.
I know this is a simple statement which is directly understood from definition of maximum. But the real impact of this statement is that it allow us to answer each query in O(log(N)) time, which is fast enough for our need.
From above statement, it follows that if MX[U] \leq W, then for all ancestors X of node U, MX[X] \leq W.
Suppose for query (V, W), we find a node X on path from root to node V such that MX[X] \leq W and MX[C] > W, where C is direct child of X on path to V. Then, we know that Number of times Maximum value changes from W to MX[V] is same as Number of times Maximum changes from root to V less Number of times Maximum changes from root to Node X.
So, now we know that if we can find this node X efficiently, we have solved the problem, Right?
A simple method of checking every ancestor of V will result in O(N) time in worst case (Linear chain), which will time out, due to overall complexity O(Q*N).
How can we utilize the fact that MX[X] \leq W for all ancestors of X. We can use the concept of Binary Lifting.
A brief Description of Binary Lifting using Sparse Table follows, so i hope those who do know binary lifting will let their attention wander freely and feel free to skip this paragraph
We create a 2dimensional array table[N][logN], where table[u][i] store $2^i$th parent of node u. How to fill this table? We know that table[u][0]  1st parent of u, that is, direct parent of u, is already known from dfs. Now, We fill our table as follows.
Since 2^{i+1} = 2^i + 2^i, which means, that $2^{i+1}$th parent of u is same as $2^i$th parent of node which is $2^i$th parent of u. This means that table[u][i+1] = table[table[u][i]][i]
That’s all about binary lifting. Generally We iterate from LogN1 to 0, having a test condition which tells us to move 2^i steps or not in ith iteration.
Returning to our problem, we can create the sparse table easily. Then try to formulate Test Condition which will tell us, whether to jump to table[u][i] or not. Here, we will move to node Y such that MX[Y] > W and all ancestors of Y have MX[u] \leq W. Then required node X is parent of Y.
Click to view
Test condition is just that if a node u have MX[u]\leq W, then don’t jump, otherwise jump.
Now that we have found the he node X required answer is just C[V]C[X]. Degenrate cases can be handled easily. In case MX[V] \leq W, answer is 0 as maximum value never changes. If W < MX[1], answer is simply C[V].
I’ll be updating links/more references soon.
TIME COMPLEXITY
Preprocessing time for sparse Table  O(N*logN), query time O(logN).
So, Overall Complexity O((Q+N)*logN)
REFERENCES:
Binary Lifting
DP on Trees for further reading
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution
Tester’s solution
Editorialist’s solution
Feel free to Share your approach, If it differs. Suggestions are always welcomed.