Skip to content
CCC Python Course

Tree DP

Stage
6
Module
M6.5
Lessons
1

In this module

  • Recognize problems solvable by computing values on trees with subproblem overlap.
  • Root a tree and define a subproblem on each subtree.
  • Compute solutions bottom-up from leaves to root.
  • Rerooting: compute solutions at every node without recomputing from scratch.

Before this module

M5.8Trees I: rooting, parent/order arrays, pruning and diameterM4.11Memoization and introductory dynamic programming

Lessons

  1. 1Tree dynamic programming

Practice

Try this on the judge. The link opens the problem on WMOJ.

  1. 2022 S5
    Good Influencers (opens on WMOJ in a new tab) WMOJ

    Keep several states per node and combine children in post-order to satisfy a tree-wide condition.