Line Tree

From neal’s blog

by Kaban-5

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 vv and uu 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_2⁡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.