Given a tree, for each node find the Kth smallest distance to the other nodes?

Revision en1, by z4120, 2020-04-09 14:09:55

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), there's not much faster (the constant factors might even make it slower). Is there a faster solution?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English z4120 2020-04-09 14:17:50 5
en2 English z4120 2020-04-09 14:10:50 0 (published)
en1 English z4120 2020-04-09 14:09:55 1288 Initial revision (saved to drafts)