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
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 ?
1 Like
Yes to all of the questions you asked.
1 Like
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 ?
If you look at @l_returns code, you will see that he is calculating the values for all nodes.
B_V and S_V are nothing but corresponding values of node v. We already know a method to find these values for a node i. Just use (or recycle) it to find for node v.
Eg - We iterate from smallest to largest node and find B_S and S_S for them. If our node in question is child of node currently assigned a2, then these values become B_V and S_V respectively.
pair<ll,ll> dp[n];
for(int i=0;i<n;i++)
{
dp[i] = make_pair(end_idx[i]-start_idx[i]+1,query(segtree,0,n-1,0,start_idx[i],end_idx[i]));
update(segtree,0,0,n-1,start_idx[i]);
}
This is my code which calculates size of the subarray and number of nodes smaller than the node in its subarray. It’s working perfectly fine, I’ve checked it thoroughly.
Now please tell how do I calculate Bv and Sv from here.
to calculate Bt and St ? or Bs and Ss ?
Talking about functions find_c1, find_c2 and find_c3 ?
You are saying that Bv and Sv for node a2 (where v is one of a2’s children) is the same Bs and Ss for the node v ?
Yes, and thats what the editorial defined them as. If this is not clear to you then you havent understood the problem/editorial and are just mimmicking the implementation. I’d suggest to give it a read, and resolve this Q after a while.
1 Like
They are numbered in the order of increasing size. Please explain the meaning of this line.
Can you quote the exact line?
Every sentence make sense.Good job @vijju123 hope to see more editorials of you on some medium hard problem.
3 Likes
Chef’s restaurant system is a tree with NN vertices, where each vertex is one of his precious restaurants. Just like with Gordon’s restaurants, they are numbered in the order of increasing size.
Thats not in the editorial, but the problem statement. If the question is not clear then you can read the version in the editorial for clarity.