Graph Theory37 sections · 1633 units
Open in Course

Down Pass (Computing subtree answers)

(Subtree DP)

Pick node 11 as the arbitrary root. Run DFS. For each node vv, compute down[v] = the answer for the subtree rooted at vv. This uses standard tree DP. This is tree DP. You combine answers from all children of vv to get down[v]. The recurrence depends on the problem. For sum of distances, you add child contributions plus edge costs. After this pass, you know down[1] = the answer when node 11 is root.

But you still need answers for all other roots. That is what the second pass does.