From neal’s blog
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 treeof a treewith weighted edges is such a tree with weighted edges, that:
- andhave the same set of vertices.
- The maximum weight on the path between vertices vv and uu is the same for treesand.
- 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 forboils 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 inwith the largest weight, remove it, build line trees of two remaining connected components and connect them with an edge with weight. This can be done inwith some small-to-large tricks and even inafter sorting with linked list merging. The second property is easy to prove by induction over such construction.
- 2019年11月20日 创建文章