Tree Paths of Length K — Solution & Editorial

Back to the Problem

Rooted DP: cnt[u][d] = nodes at depth d within u's subtree. When merging a child, pairs passing through u combine depths summing to K−1; then shift and add the child's counts. (Centroid decomposition scales to N = 10⁵.)

Complexity: O(N·K)

Watch out: Count pairs BEFORE merging a child, or a node pairs with itself's subtree twice.