Vertex reindexed by indexHLD.

HLD splits a tree into lines. Lines are often called "paths", but here we say "lines" for avoiding word conflicts.

Example

Original tree

Consider a tree with arbitrary vertex order:

 0--8--7--3--1--2--12--13--15--14     XX: vertex
    |        |                         --: edge
10--5        11--8--6                   |: edge
    |
    4

indexHLD: Vertex -> vertexHLD

The tree vertices are reindexed with indexHLD, ensuring vertices in each line have consecutive numbers:

 0==1==2==3==4==5==6==7==8==9     XX: vertex
    |        |                     ==: edge on the same line
14==13       10==11==12            |: edge between different lines
    |
    15

Note that vertices on higher lines are assigned smaller numbers.

headHLD: Vertex -> Vertex

headHLD can be used for finding LCA of two vertices. To find the LCA, move up to the head, go up to the parental line's vertex and repeat until they are on the same line.

 0==0==0==0==0==0==0==0==0==0
    |     |
 5==5      11==11==11
    |
    4

headHLD also works for identifying lines. When two vertices are on the same line, they have the same head.

parentHLD: Vertex -> Vertex

parentHLD lets you go up to the parental line's vertex from a head:

(-1)==0==8==7==3==1==2==12==13==15
      |        |
   5==8        1==11=8
      |
      5

Segment tree integration

With HLD, we can find a path between two vertices u, v: u -> lca(u, v) -> v. The path is decomposed into segments where segment trees can be integrated as in TreeMonoid.

Vertex monoid folding on a path

If vertices have weights, use foldVertsCommuteHLD or foldVertsHLD.

Edge monoid folding on a path

If edges have weights, you can either treat the edges as new vertices or assign edge weights to the depper index.

Idea 1. Treat edges as new vertices.

       convert
o--o--o  --> o-x-o-x-o

Idea 2. Assign edge weight to the deeper vertex. This is the idea of foldEdgesCommuteHLD and foldEdgesHLD:

  o
  | <--- edge 1
  o <- write wegiht 1 here
  | <--- edge 2
  o <- write wegiht 2 here

Subtree folding

Subtree VertexHLD is contiguous. We can easily find the corredponding (l, r) paris of VertexHLD that corresopnds to the subtree by remembering the subtree sizes.

\(O(V)\) Constructs HLD.

\(O(V)\) Constructs HLD with root vertex specified.

\(O(\log V)\) HLD calculation.

Typical Problems

ABC 133 - F

\(O(\log V)\) Path length between two vertices.

\(O(\log V)\) Shared implementation of edgeSegmentsHLD and vertSegmentsHLD, which returns `[l, r]` pairs for each segment.

• The return type is VertexHLD.
• Note that each (l, r) pair can be l > r.
• LCA is omitted when isEdge parameter is set to True (the trick to put edge weights to vertices).

\(O(\log V)\) Returns inclusive edge vertex pairs.

\(O(\log V)\) Returns inclusive vertex pairs per.

\(O(\log^2 V)\) Folds path between v1 and v2. Use specialized methods for simplisity.

\(O(\log^2 V)\) Folds commutative monoids on a tree edges using HLD. Prefer to use the wrapper TreeMonoid.

Typical Problems

• ABC 294 - G

\(O(\log^2 V)\) Folds commutative monoids on a tree vertices using HLD. Prefer to use the wrapper TreeMonoid.

TODO: verify

\(O(\log^2 V)\) Folds commutative monoids on a tree vertices using HLD. Prefer to use the wrapper TreeMonoid.

Typical Problems

• Vertex Add Path Sum - Library Checker

\(O(\log^2 V)\) Folds non-commutative monoids on a tree vertices using HLD. Prefer to use the wrapper TreeMonoid.

Typical Problems

• Vertex Set Path Composite - Library Checker

\(O(1)\) Returns (start, end) VertexHLD that corresponds to the subtree segments rooted at the subtreeRoot.

\(O(1)\) Returns True if u is in a subtree of r.

\(O(\log V)\) Go up i times from the parent node to the implicit root node.

\(O(\log V)\) Returns i-th vertex of a path between u, v.

https://judge.yosupo.jp/problem/jump_on_tree

\(O(\log V)\) Returns path between u and v.

HLD wrapper for folding paths on a tree using HLD and segment tree(s).

\(O(V)\) Shared implementation of buildVertTM and buildEdgeTM.

\(O(V)\) Builds a TreeMonoid on vertices.

\(O(V)\) Map weightened edges into (Vertex, a) pairs. The output is the input to buildEdgeTM.

\(O(V)\) Builds a TreeMonoid on edges. **The input must be the output of edgeVertsHLD**.

\(O(\log^2 V)\) Folds a path between two vertices.

\(O(\log V)\) Folds commute monoids on vertives of a subtree.

\(O(\log V)\) Folds commute monoids on edges of a subtree. TODO: test

\(O(\log V)\) Reads a TreeMonoid value on a Vertex.

\(O(\log V)\) Write a TreeMonoid value on a Vertex.

\(O(\log V)\) Exchanges a TreeMonoid value on a Vertex.

\(O(\log V)\) Modifies a TreeMonoid value on a Vertex.