Fixed-Length Paths I - Implementation

Here is the centroid decomposition for fixed-length paths:

function fixedLengthPaths(n, adj, k):
    removed = array of size n, all false
    answer = 0

    function getCentroid(u, parent, treeSize):
        // Same as standard centroid finding
        ...

    function countPaths(u, parent, dist, centroid):
        if dist > k:
            return
        pathCount[dist] = pathCount[dist] + 1
        for v in adj[u]:
            if v != parent and not removed[v]:
                countPaths(v, u, dist + 1, centroid)

    function solve(u):
        treeSize = getSubtreeSize(u, -1)
        centroid = getCentroid(u, -1, treeSize)
        removed[centroid] = true

        pathCount = map from distance to count, initially empty

        for v in adj[centroid]:
            if not removed[v]:
                // Count paths through centroid
                tempCount = empty map
                countPathsToTemp(v, centroid, 1, tempCount)

                for (d, cnt) in tempCount:
                    if k - d >= 0 and pathCount[k - d] exists:
                        answer = answer + cnt * pathCount[k - d]

                // Merge into main count
                for (d, cnt) in tempCount:
                    pathCount[d] = pathCount[d] + cnt

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

    solve(0)
    return answer

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