Graph Theory37 sections · 1633 units
Open in Course

Section Recap

(Pattern recognition summary)

You practiced recognizing which tree technique fits each problem:

• Subordinates: Simple subtree DP. One DFS, count sizes.

• Tree Diameter: Two approaches. Double BFS or DP tracking max depths.

• Tree Matching: Subtree DP with states. Track whether node is matched.

• Tree Distances II: Rerooting. Compute for one root, then shift answers.

• Choosing Capital: Rerooting with directed edges. Track reversal cost changes.

• Max White Subtree: Combine subtree DP with rerooting for global answers.

The core skill: read the problem, identify what's being asked (subtree values, global values, all-roots answers), then pick the right technique.