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: . Space: .