I am not able to understand the editorial for Treeversion . I went through the editorial and the code also still not getting it. Kindly help
1 Like
Okay so here is a try:
A few minutes ago, even I was struggling with the intuition for the comparator. You will realize that the comparator is the only thing in the problem.
Consider the subtrees at p and q. We can order them by the comparator:
ones_p*zeros_q \lt ones_q*zeros_p
Note that we assume that p and q have their children ordered correctly (they have the minimum inversions among themselves). Now, we need to ensure that the number of inversions due to ordering of p and q is minimum.
If we place p before q, the number of extra inversions (apart from the ones that p and q have among themselves) is ones_p*zeros_q (the 1s in p that come before the 0s in q, choose one of the 1s and one of the 0s and you get an inversion). Similarly, if we place q before p, we have ones_q*zeros_p inversions. We place the one which has lesser inversions first.
You order sub-trees using this and then find the number of inversions. I have used multiple DFSs in my solution but it can be done with a single DFS.
3 Likes
Thanks ankit for helping me, it was really helpful.
(They don’t allow posts less than 20 characters 
)
1 Like
Yes it clear that comparator works for one pair, but how can we prove that it works for n elements in general?
Suppose comparator works for a pair. Now at any time, you can choose two elements of the list and swap them according to this comparator and get a better answer. You keep picking elements two at a time and keep swapping them. You will keep on getting better answers till it is possible to sort elements according to comparator, and once it is fully sorted according to comparator, swapping any two elements will give a worse answer.
3 Likes
Actually, the idea of comparator is that it defines an ordering for subtrees, just like ordering for numbers. Once you define how to order subtrees, you know how to sort the subtrees.
If you know how to compare two numbers, you can sort a list, right?