This was my approach for this problem which I reckon may not be the most optimal way of solving it. But it worked nevertheless. If we have the n distances from a node (including itself), we can calculate the kth largest distance. This number  1 would be our answer for that node. Solution: We fix a root node (say node 1) and calculate the distances of all the nodes from it. Now to find the distances from a child node, we can see that for all the distances in the subtree of the child node, we need to subtract 1 from the distances and for all the distances not in the subtree, we need to add 1 to the distances. We observe that, if we store in an array the preorder traversal of the tree, each subtree will be a contiguous range in that array. In fact, postorder or inorder traversal would also work, but let's consider preorder for the sake of this editorial. Now the task simplifies to this: 1) Create an array from preorder traversal of the tree and store the start and end array indices for each node of the tree  DFS  O(N) 2) Calculate the distances of all the nodes from the root node (including itself)  DFS  O(N) 3) Using DFS, whenever we go from parent node to child node, subtract 1 from the range denoting the subtree of child and add 1 to the remaining values (left range and right range). We will do this using sqrt decomposition on the array. We will discuss more below. 4) Calculate the Ki th largest value in the complete array. Data structure and algorithm is discussed below. Data Structure: We will be working on the array that we have created. Let's take bucket size b. Now partition the array into buckets, b elements in each bucket. For each bucket we will be storing 2 values. (1) a sorted list of values in that bucket (C++ vector) (2) lazy value = 0, we'll discuss it's use soon. Let's look at range update. Exactly like sqrt decomposition, for every node completely in the range, we just add or subtract 1 to the lazy value of that bucket. Otherwise we rebuild the particular bucket, for all the values in the bucket we calculate the new value brute force and sort these values. Note: lazy value is not changed in this case. Time Complexity  O(N/b + blog(b)) For querying the kth largest in the current array, we do this. Let's consider for the time being that all lazy values are 0. I'll discuss a binary search approach to get the kth largest element. Let's say I define a function lessthanx which will tell you the number of items in the whole array less than x. We can calculate this simply by calling lower_bound on all the buckets. This would be O(N/b * log(b)) Now let's remove the restriction on the lazy value. We can see that the lazy value doesn't alter the relative positioning of the values inside a bucket, so while querying lessthanx, we can simple call lower_bound on xlazy to get our answer. We can apply binary search on x to find the position (or distance) such that it's the kth largest element in the whole array. Time Complexity  O(log(N) * N/b * log(b)) We have to do all these in our main DFS, 1) update: the subtree range 1 and rest of the ranges +1 2) query on the current array for the required kth largest element 3) unupdate: the subtree range +1 and rest of the ranges 1 Total time complexity  N * (N/b + blog(b) + log(N) * N/b * log(b)) = O(N * (blog(b) + log(N)(N/b)*log(b))) We can choose the value of b to minimize the time complexity. Hope this helps! Suggestions are welcome! asked 13 Feb, 18:20

My Soln  answered 13 Feb, 18:35
@aryanc403 That's a lot of searching :D I'll have a look at the video, seems interesting. Thanks!
(13 Feb, 18:57)
wtf do you google search bro. Plz tell :p
(13 Feb, 19:23)
I'm not the only person there.
(13 Feb, 19:40)
Dont try to dodge the question :p
(13 Feb, 19:46)
Even I got this question from quora's blog of Tanuj Khattar.
(14 Feb, 01:16)
LOL If I would have found this then I would have copy pasted Author's code :P
(14 Feb, 12:25)
showing 5 of 6
show all

Did anyone else do this with centroid decomposition+persistent seg tree? answered 13 Feb, 20:28
I solved it using centroid decomposition + LogN BIT.
(13 Feb, 20:43)
@aryanc403 can u explain your approach?
(14 Feb, 02:40)

My Soln  answered 14 Feb, 12:42

My soln  Read the problem statement. Realize that I have solved a similar problem before that was almost same except for the initial binary search. Code it and after a few implementation mistakes get it AC. BTW, here's that problem: https://www.hackerearth.com/challenges/competitive/novembereasy18/problems/ answered 14 Feb, 16:50

Please add the word "Unofficial" to the title. People may believe that this is the official editorial just like I did.
It never occurred to me. Thanks!
Thanks for sharing this approach! This makes the problem much more approachable.
You're welcome. I concur that this isn't the most optimal way of solving it but my aim was to encourage people to explain their approach. And fairly enough, I now know what Centroid Decomposition is :D