When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

z4120's blog

By z4120, history, 4 years ago, In English

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?

  • Vote: I like it
  • +43
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +26 Vote: I do not like it

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.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think I have little bit easier solution, using parallel binsearch and centroid decomposition, but it is still $$$O(nlog^3)$$$