Implementation Tips

Here is the centroid decomposition implementation:

function centroidDecomposition(n, adj):
    removed = array of size n, all false
    centroidParent = array of size n, all -1

    function getSubtreeSize(u, parent):
        size[u] = 1
        for v in adj[u]:
            if v != parent and not removed[v]:
                size[u] = size[u] + getSubtreeSize(v, u)
        return size[u]

    function getCentroid(u, parent, treeSize):
        for v in adj[u]:
            if v != parent and not removed[v]:
                if size[v] > treeSize / 2:
                    return getCentroid(v, u, treeSize)
        return u

    function decompose(u, parent):
        treeSize = getSubtreeSize(u, -1)
        centroid = getCentroid(u, -1, treeSize)

        centroidParent[centroid] = parent
        removed[centroid] = true

        for v in adj[centroid]:
            if not removed[v]:
                decompose(v, centroid)

    decompose(0, -1)
    return centroidParent

Time: $O(n \log n)$. Space: $O(n)$.