Hello everyone, I need help with approaches to a tree problem I couldn’t solve.

Any ideas on how to solve this tree problem efficiently?

Here’s my approach using binary search.

If i read the question correctly on hackerrank,

The value of n is 105

then the problem can be solved in O(n^2*log(n)).

I designed approach which uses preorder traversal pattern to identify the structure of k_subtrees. I explained my approach using sample example given on hackerrank.

My approach basically uses unordered_map for hashing preorder pattern for every vertex for particular k logn times obviously using Binary search for answer concept.

Actually in photo i wrongly calculated complexity as n^3logn but its actually n^2logn if you see carefully

Hope to listen from you as fast as possible

I’m sorry that you had to read it like that. It’s actually 10^5 and not 105; they formatted it wrong. Also, you should’ve seen my binary search solution. We want an O(n lgn) or O(n \cdot lg^2n) solution.

So are you getting TLE or WA in some cases

TLE

Yaa, you are right, I could only get

57.14 points

with my approach

If you find any better solution, plz let me know