Here's the construction:
function buildHLD(root)
// First DFS: compute subtree sizes
dfs1(root, -1)
// Second DFS: assign positions
currentPos := 0
dfs2(root, -1, root)
function dfs1(v, parent)
subtreeSize[v] := 1
for each child u of v (u ≠ parent)
dfs1(u, v)
subtreeSize[v] := subtreeSize[v] + subtreeSize[u]
if subtreeSize[u] > subtreeSize[heavyChild[v]] then
heavyChild[v] := u
function dfs2(v, p, head)
parent[v] := p
chainHead[v] := head
pos[v] := currentPos
currentPos := currentPos + 1
if heavyChild[v] exists then
dfs2(heavyChild[v], v, head) // Continue chain
for each child u of v (u ≠ parent, u ≠ heavyChild[v])
dfs2(u, v, u) // Start new chain