PROBLEM LINK:Practice Setter: DOlaBMOon 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
EXPLANATIONFirst 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 :P 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 :D 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$. 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 COMPLEXITYPreprocessing time for sparse Table  $O(N*logN)$, query time $O(logN)$. So, Overall Complexity $O((Q+N)*logN)$ REFERENCES:Binary Lifting AUTHOR'S AND TESTER'S SOLUTIONS:Setter's solution Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)
This question is marked "community wiki".
asked 23 Sep '18, 12:36

Very nicely explained editorial :)..........BTW can anyone help me why my solution gives a TLE , I followed just the editorialist's approach. answered 25 Sep '18, 01:32
3
It is better to use iterative DFS, wherever possible, Because it reduces recursive calls time as well as stack memory consumption (especially for java). Rest all seems right. Glad you liked editorial.
(25 Sep '18, 01:43)
Thanks @taran_1407, got it AC'ed with iterative DFS :)
(25 Sep '18, 02:10)
1
And in this part of the editorial there is a typo .. 2^(i+1) = (2^i) * (2^i) ... it will be 2^(i+1) = (2^i) * 2. Please edit that part..
(25 Sep '18, 02:13)
No problem :)
(25 Sep '18, 02:14)
@taran_1407 can you say is the recursion depth for JAVA < 1e6 , which may be the reason for TLE ?
(25 Sep '18, 02:28)
Not excatly recursion depth, but the revursive calls. The iterative version is usually faster, as recursion stack slow down, when too much calls are in stack.
(25 Sep '18, 02:44)
showing 5 of 6
show all

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]≤W, answer is 0 as maximum value never changes. If W < MX[1], answer is simply C[V]. What is the difference b/w these two implementations ? First one got WA Second got AC First One
SECOND ONE
Thanks!! answered 04 Oct '18, 19:58
First One : https://www.codechef.com/viewsolution/20459971 Second One : https://www.codechef.com/viewsolution/20460002
(04 Oct '18, 20:01)
