Recently I came across a problem (source)
Translated problem statement:
Given a tree of N points and an integer K. Each edge has a weight. You need to calculate for each node i; what is the Kth smallest value within the distances to the other N-1 nodes.
Data size: 1 ≤ K < N ≤ 50000, the weight of the edge is an integer whose absolute value is less than 1000.
The described solution there uses sqrt decomposition. The author also left a footnote (translated):
This problem has a solution with better time complexity but very complicated tree chain splitting.
I used heavy-light decomposition, small-to-large merging and persistent treap, and come up with a solution which (I think) have time complexity $$$O(n \log^3(n) + n \log^2(n) \log(n × \text{max edge weight})$$$).
In comparison with the sqrt decomposition (with time complexity $$$O(n^{1.5} \log^{1.5} n)$$$ according to the linked page), that's not much faster (the constant factors might even make it slower). Is there a faster solution?
Why downvote anyway? This is not a basic problem. And I did describe my attempt. Should I explain it in more details?
I searched this on the Internet too, but Google isn't good at searching for competitive programming problem statements.
I think I have little bit easier solution, using parallel binsearch and centroid decomposition, but it is still $$$O(nlog^3)$$$