Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

### z4120's blog

By z4120, history, 2 years ago,

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?

• +43

 » 2 years ago, # |   +26 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.
 » 2 years ago, # |   0 I think I have little bit easier solution, using parallel binsearch and centroid decomposition, but it is still $O(nlog^3)$