neal's blog

By neal, 3 weeks ago, In English,

Inspired by the discussion at Almost-LCA in Tree, I wanted to pose a similar question:

Is there a simple solution to

  1. preprocess a tree with weighted edges in $$$O(n)$$$ or $$$O(n \log n)$$$ and
  2. query the maximum edge weight along the path from $$$u$$$ to $$$v$$$ in O(1)?

Once again, jump pointers can be used to solve each query in $$$O(\log n)$$$ with bad constant factor. Are there faster solutions?

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

»
3 weeks ago, # |
  Vote: I like it +26 Vote: I do not like it

I think the method I described here can be extended to answer this.

»
3 weeks ago, # |
Rev. 2   Vote: I like it +155 Vote: I do not like it

There is the following nice technique called "line tree". I do not know the exact origin of this trick: I learned it from editorial of a recent contest by 300iq.

Formally, a line tree $$$L_T$$$ of a tree $$$T$$$ with weighted edges is such a tree with weighted edges, that:

  1. $$$L_T$$$ and $$$T$$$ have the same set of vertices.
  2. The maximum weight on the path between vertices $$$v$$$ and $$$u$$$ is the same for trees $$$T$$$ and $$$L_T$$$.
  3. $$$L_T$$$ is, well, a line (so we can choose the order of the vertices on the line and the weights of edges between neighbouring vertices, but nothing else).

If we already have a line tree, answering "maximum weight on a path" queries for $$$T$$$ boils down to asking maximum on a subsegment of an array, which can be done with a sparse table.

How to construct a line tree efficiently (even its existence is not obvious)? We can do it recursively: pick an edge in $$$T$$$ with the largest weight $$$w$$$, remove it, build line trees of two remaining connected components and connect them with an edge with weight $$$w$$$. This can be done in $$$O(n \log n)$$$ with some small-to-large tricks and even in $$$O(n)$$$ after sorting with linked list merging. The second property is easy to prove by induction over such construction.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +42 Vote: I do not like it

    Yeah, I come up with this technique in May 2018, but I heard it was well-known long time ago and in China it's called with some name similar to "Kruskal Tree" or smth

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Hi Kaban-5, may I ask which question was that, which u learnt the trick from? Thanks in advance :)

    • »
      »
      »
      3 weeks ago, # ^ |
      Rev. 4   Vote: I like it 0 Vote: I do not like it

      Unfortunately, there may be some "legal" problems with sharing the statement and editorial of this contest :(. All links in the first edit level are now dead.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        Oh, then Kaban-5 are u allowed to describe just that problem or something? rather than sharing the whole editorial? If not is someone else able to give some other problems which utilises the trick? or at least describe some common scenarios in which this can be used? Thanks in advance, sorry for the trouble.

»
3 weeks ago, # |
  Vote: I like it +41 Vote: I do not like it

Let's run Boruvka on the given tree (it will work in $$$O(n)$$$ because it's tree).

With it we can build a tree with $$$O(\log)$$$ depth with the same maximums on all paths (in each boruvka iteration create a new vertex for all connected components and connect it to all vertices (not initial vertices, but connected components at the start of current boruvka iteration) with weights of edges that you add to MST on current iteration). Now we can use jump pointers on this tree to answer queries in $$$O(\log \log n)$$$. Also with 4-Russians method you can make it work in $$$O(1)$$$, and this technique is used in linear MST algorithm.

»
3 weeks ago, # |
Rev. 2   Vote: I like it +28 Vote: I do not like it

In $$$O(n~log~n)$$$ you can build centroid decomposition on this tree. Then, to answer a query you need to find LCA of $$$u$$$ and $$$v$$$ in a tree of centroids (that can be done in $$$O(1)$$$ as LCA for usual tree) and take precalced maximums on paths from $$$u$$$ and $$$v$$$ to this centroid.

»
3 weeks ago, # |
Rev. 2   Vote: I like it +47 Vote: I do not like it

Use the Kruskal algorithm, each time you add a edge $$$u\leftrightarrow v$$$, create a new vertex $$$k$$$ which left son is the disjoint set of $$$u$$$ and right son is the disjoing set of $$$v$$$.

Then the answer of the query $$$(u,\,v)$$$ is the lowest common ancestor of $$$u$$$ and $$$v$$$. It can be done in linear time.

Sorry for my poor English.

»
3 weeks ago, # |
  Vote: I like it -26 Vote: I do not like it

Assuming there is no update to the tree, i think we can just use RMQ LCA using 2 sparse table, one for getting LCA, one for tracking maximum value of edges so far. We could use O(1) query on sparse table using most significant bit. I think there is a resource about LCA using RMQ in Competitive Programming 3 Book by Steven Halim.

Let's say we have to query path(u,v), we get their LCA using RMQ LCA in O(1) denote as anc, we know how much we need to lift from u and v, then we can just look the the sparse table which track for maximum value then query from u to anc and from v to anc and get maximum of two of them.

Assuming i'm understanding your post correct i think that should work right?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    How do you get the maximum on path from $$$u$$$ to $$$lca(u, v)$$$ faster than $$$O(\log(n))$$$?

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      My bad, i didn't think it through about the maximum query, i thought i would be possible alongside the sparse table used to get the lca(u,v), and yes it's complexity is still $$$O$$$(log($$$n$$$)) at its best.