How to represent each subtree by a subarray of an array ?
Answer is using “Euler tour”.
Each subtree will be represented by a range (l,r) in euler tour.
This is the application of euler tour in this problem.
s[node]=l ( this is what s[node] stores)
e[node]=r ( this is what e[node] stores)
Basically subtree with root = node will be represented as subarray starting at index l and ending at index r.
You can refer to @l_returns ’ code for implementation. The first point is typical Euler tour on a tree, and I feel 2nd and 3rd point are sufficiently explained. Whats not clear to you?
I can understand you cuz I have been there few months ago 
This question has 4-5 big parts. One can’t tackle all of them if they don’t have the pre-requisites.
So, I would suggest you to practice 4-5 problems on flattening of tree into an array from here :-
Then only come back to this editorial.
@anon55659401 @vijju123 @l_returns, Thank you very much for your advice and help 
.
I will surely do the questions recommended by Karan …
Well, it looks like that the s[] and e[] are storing values of timestamps ( s[node] storing the time when node was first discovered and e[node] stores the value of finishing time when each node of its subtree was fully discovered ), am I right about this time stamping thing ?
I understood @l_returns solution , but this “time stamping” operation is slightly different from what I’ve studied in my class.
Example : For this tree (given below in image) this should be the starting and finishing times represented by s/e (written in pencil) for each node …
but according to the implementation it is giving output as :-
S[] = 0 1 2 3 4 5 6
E[] = 6 3 2 3 6 5 6
Yes, you are right about timestamps. AFAIK, both approaches will be correct, just that his approach is more memory efficient.
Hey, your account seems non-existent🤔
non-existent ? why ?
Euler tour array :
index : 0 1 2 3 4 5 6
value : 1 2 3 4 5 6 7
Now subtree 1 contains all 7 nodes hence s[1]=0 (index in euler ) , e[1]=6 (index)
Now subtree 2 contains 2,3,4 hence s[2]=1 , e[2]=3
Now subtree 3 contains 3 hence s[3]=2 , e[3]=2
Now subtree 4 contains 4 hence s[4]=3 , e[4]=3
Now subtree 5 contains 5,6,7 hence s[5]=4 , e[5]=6
Now subtree 6 contains 6 hence s[6]=5 , e[6]=5
Now subtree 7 contains 7 hence s[7]=6 , e[7]=6
The double-underscore bug strikes again! wingman__7 | CodeChef User Profile for SomnAth Pal | CodeChef
As far as I remember, for each node, you need to the know number of nodes greater/smaller than this in its subtree. Also, you need to know for each node, the number of nodes greater/smaller than it in the whole tree except the subtree…
Seems like there is some issue with discuss.
It is considering double underscore as single
Okay I understood your doubt.
Yeah there are two ways
One is 2n (all nodes will be inserted twice) and one is n.
You can use either depending on application
Yes , I figured that out a few days ago but I was a little bit confused about this time stamping thing . Anyways thanks again , my problem is solved now …
Yes I got that part 
We get the size of subtree of a node by e[node]-s[node]+1, which I understood. But this number of nodes smaller than node in the subtree of node (i.e. Ss value of node), how are we getting the values ? I understood the query function which calculates sum (which is actually sum of 1’s) from s[node] to e[node].
I printed the dp[x] (which is an array of pair<>) for input of 0-1; 0-3; 3-2; 3-4 .
The final answer is 3 which is perfectly fine. But node 3 has node 2 in its subtree which is smaller but in the output for node 3 the value is 3 0 (here 3 is the size of subtree which is correct and 0 is the number of nodes smaller than node 3 in its subtree). I think the output should be 3 1.
Also for node 2 the value of the second column should be 0 because there is no subtree under it (it’s a leaf node).
pls help
In the array, we know that the range [Start[i],End[i]] denotes the subtree of node i where Start[i] is the time when we entered the node and End[i] is the time when we exited the node.
Now, we iterate through the nodes from smallest to largest. For each node, we do the following-
Since all values are either 0 (if node is larger and hence the value is not yet made 1), or 1 (this node is smaller and its value is updated already), we just do a range sum query to find number of elements smaller than i.
this part is done by the query function
the appropriate index you are talking about is s[i] ???
To get the number of nodes smaller than a particular node in its subtree we just need to execute a range sum query with s[node] and e[node] as starting and ending query indices ?
Yes to all of the questions you asked.
Hey, I got that part … Thanks a lot for your help. I’m now very close to the solution.
So I’ve computed Ss (number of nodes smaller than the node in it’s subtree) and total number of nodes present in the subtree of that node for every node in the whole tree. Now, how do I calculate this Bv and Sv ? What is meant by this recycle the same method ?
