If a problem hands you a tree and asks for "the best path," "the maximum independent set," or "the answer at every node," there is a good chance the intended solution is DP on trees.
Dynamic programming on trees is one of the highest-leverage techniques a competitive programmer can learn. It shows up constantly at the upper levels of contests, and on platforms like Codeforces and USACO it is treated as a core Gold-division skill that you will keep using all the way into Platinum. The good news: once the core idea clicks, a whole family of problems starts to look the same.
What Makes a Problem "DP on Trees"
The central insight is that a tree naturally breaks a big problem into smaller, non-overlapping ones. Each node defines a subtree, and the answer for a node usually depends only on the answers of its children. That recursive structure is exactly what dynamic programming exploits.
Every tree-DP solution begins with one question: what does a parent need to know about each child's subtree? That answer becomes your DP state. Common states include:
- The longest downward path from a node to any leaf in its subtree.
- The number of nodes, or the sum of weights, contained in a subtree.
- Two values per node, such as "best answer if this node is included" versus "excluded" (the classic for maximum independent set).
Designing the right state is the hard part. Coding the traversal, as you will see, is almost mechanical once the state is correct.
The Post-Order Pattern
Because a node's answer depends on its children, you must compute children before the node itself. That means a single post-order DFS: recurse into every child, then combine their results to fill in the current node. Because you visit each node and each edge exactly once, the whole computation runs in O(N) time for a tree of N nodes.
A clean way to think about it:
- Root the tree at any node (often node 1 or node 0).
- Run a DFS. For each node, first recurse into all children.
- Merge the children's DP values into the parent's state.
- Return the parent's value to its own parent.
Notice the pattern: the answer is "the best path whose highest point is this node," maximized over every node. That reframing — anchor the path at its topmost vertex — is a recurring trick worth internalizing.
Rerooting: Answers for Every Node
Sometimes you need an answer for each node as a root — for example, "for every node, the sum of distances to all other nodes." The naive approach runs a fresh DFS from every node, which is O(N²) and far too slow for large inputs.
The rerooting technique solves this in O(N) with two passes. The first is the usual bottom-up DFS that collects subtree information. The second is a top-down DFS that pushes each parent's contribution back down to its children, so every node learns about the "rest of the tree" hanging above it. Combining the downward subtree value with this upward value gives the full answer at that node.
Rerooting is best understood as a way to convert "run a DFS from every root" into a single, reusable computation. If your brute force is N independent DFS calls, reach for rerooting.
Watch out for the common pitfall: when you reroot from a parent to a child, you must remove that child's contribution from the parent's aggregate before passing it down. Getting that subtraction right (or using prefix/suffix combinations to avoid division) is where most bugs hide.
How to Practice It
Tree DP rewards repetition. Start by re-deriving the three canonical problems — subtree size, tree diameter, and maximum independent set — from scratch until the post-order skeleton is automatic. Then move on to rerooting problems, which combine everything. The USACO ladder is an ideal proving ground, since tree DP appears regularly in its Gold contests, and broader contest practice will keep exposing you to fresh variations.
At BIAA, our competitive programming program teaches these patterns the way strong contestants actually think — state design first, implementation second — with guided problem sets and code review on every submission. If you are aiming for olympiad-level algorithms, explore the program here and start turning tree problems into automatic wins.