#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/heavy-light-decomposition/implementation-preprocessing

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/heavy-light-decomposition/implementation-preprocessing

Repovive

Implementation - Preprocessing - Heavy-Light Decomposition | Graph Theory | Repovive

Repovive.

Graph Theory37 sections · 1633 units81h total

Open in Course

Implementation - Preprocessing

(Computing sizes and parents)

Run a DFS to compute size[v], depth[v], and parent[v] for each node:

function dfs_init(v, par, d)
    parent[v] := par
    depth[v] := d
    size[v] := 1
    for u in adj[v]
        if u != par then
            dfs_init(u, v, d + 1)
            size[v] := size[v] + size[u]

Call $dfs\_init(root, -1, 0)$ from the root. This single DFS computes all three arrays in $O(n)$ time. You traverse each edge exactly twice, once in each direction.

Space complexity is $O(n)$ for the data structures used.