Implementation - Decomposition

Run a second DFS to assign chains and positions:

cur_pos := 0

function dfs_hld(v, par, c)
    chain[v] := c
    if new chain then
        head[v] := v
    else
        head[v] := head[par]
        pos[v] := cur_pos
        cur_pos := cur_pos + 1
        heavy := -1
        for u in adj[v]
            if u != par and (heavy = -1 or size[u] > size[heavy]) then
                heavy := u
                if heavy != -1 then
                    dfs_hld(heavy, v, c)
                    for u in adj[v]
                        if u != par and u != heavy then
                            dfs_hld(u, v, new_chain)

This assigns positions and chains in $O(n)$ time. Process the heavy child first to keep chains contiguous.

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