You are the best editorialist, @vijju123… It kinda makes me sad that after putting such huge efforts in writing such a wonderful and super-helpful editorial, u get just 9 likes to that…anyways, keep up the good work and a hearty thanks for editorial !
4 Likes
Need Help. I am getting TLE . I followed the approach as given in second editorial. Any one can tell the reason for TLE.
@l_returns , Could you please tell me what is the purpose of arrays s[] and e[] in your solution ? what values are they storing ?
EDIT 1 : the s[] array is storing values that are smaller than that particular node… am I right?
EDIT 2 :
Can you please explain this process in a bit more detail by taking a small example (or share links maybe) ??
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.
2 Likes
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?
2 Likes
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.
5 Likes
@anon55659401 @vijju123 @l_returns, Thank you very much for your advice and help 
.
I will surely do the questions recommended by Karan …
3 Likes
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
1 Like
Yes, you are right about timestamps. AFAIK, both approaches will be correct, just that his approach is more memory efficient.
2 Likes
Hey, your account seems non-existent🤔
non-existent ? why ?
1 Like
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
2 Likes
The double-underscore bug strikes again! wingman__7 | CodeChef User Profile for SomnAth Pal | CodeChef
4 Likes
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…
1 Like
Seems like there is some issue with discuss.
It is considering double underscore as single
3 Likes
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
1 Like
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 …
1 Like
Yes I got that part 
1 Like
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-
- Find the sum of values in range [Start[i],End[i]]
- After finishing computation for this node, update the value at appropriate index to 1 and proceed to next greater node.
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.
1 Like