How about adding “hint” section here for those who still wanna solve it without looking at detailed solution or full solution ?
That section won’t reveal full solution but will give some hints.
We can have two hints. level 1 (which reveals very very less) and level 2 (which reveals little more ) ?
Not for this editorial but in general.
@vijju123 @taran_1407
1 Like
Euler Tour + BIT/segtree is usually the easy part, and my favourite one too.Without the experience of ‘INTRAPATH’, I won’t be able to solve CHOGRAM.
3 Likes
I think vijju123 is more capable than me to decide 
Usually euler tour + segtree is tough to come up with unless you have already solved that type of problem.
Also there were cases and math here.
And we had to sort queries ( that idea was also non trivial) or use some BST or OST.
So i think that might be the reason for keeping it med hard.
3 Likes
Nah. I feel pre requisites give more hint than we give them credit for. It takes efforts to write good hints which reveal just the right amount, so I prefer not having them. The same effort can go to analyzing solutions, listing tricky test cases which I feel are more useful.
2 Likes
No.
Editorial difficulty tags are not randomly allotted. They are written according to the feedback and problem feedback agreed to by the setter, the tester and the contest admin. It is rightly a medium-hard problem.
Just because you solve a problem doesnt mean you should rate it as lower difficulty - it seems as if boasting and actually demotivates people who were not able to solve the problem. 
8 Likes
Yeah Karan, we know you are a good problem solver and you solved/and are capable of solving the problem… But doesn’t mean you should downgrade the difficulty level of a problem. If this is an easy-medium problem then what’s the level of those who weren’t able to solve it? Are they all noobs? Sorry, don’t take it in a wrong but it appears bragging to me. 
Hey…hey…it was just my opinion…I felt that everyone felt that is was medium nothing else…I am not talking about myself. For me , it was very very hard. Please don’t misunderstand me…I did 75 wrong submissions to this problem…I’ll make sure not to share my idea on difficulty level in any comment. I am really sorry. And to the beginners:-This is very hard problem, trust me,very hard…
2 Likes
Don’t misunderstand me…I was adding the opinion which I heard from many people…nothing else. And this problem is very hard for me. I did 75 wrong submissions to this problem.I am also a great noob. Please don’t call me good. I don’t like it…
2 Likes
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