Tree DP
Tree DP is DP carried out on a tree. Because a tree is inherently recursive, tree DP is usually done by recursion.
Basics
The following problem shows how tree DP usually goes.
Example: Luogu P1352 A Party Without the Boss
A university has \(n\) employees, numbered \(1 \sim n\). They are organized in a hierarchy: their relations form a tree rooted at the president, in which every parent is the direct superior of its children. An anniversary party is coming up, and every employee who is invited adds a certain happiness index \(a_i\). However, if an employee's direct superior comes to the party, that employee will refuse to come no matter what. Write a program that works out which employees to invite so that the happiness index is as large as possible, and find this maximum.
Let \(f(i,0/1)\) be the optimal solution for the subtree rooted at \(i\) (the second dimension is 0 when \(i\) does not attend the party and 1 when \(i\) attends).
Every state has two decisions (below, \(x\) always stands for a child of \(i\)):
- If the superior does not attend, each subordinate may or may not attend, so \(f(i,0) = \sum\max \{f(x,1),f(x,0)\}\).
- If the superior attends, no subordinate attends, so \(f(i,1) = \sum{f(x,0)} + a_i\).
We run a DFS and update the optimal solution of the current node when the recursion returns to the level above.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | |
The state in tree DP is usually the optimal solution for the current node. A DFS first works out the optimal solutions of all the subtrees, which are then passed up to each subtree's parent for the transition. The value at the root is the optimal solution we are after.
Practice problems
Tree knapsack
A knapsack problem on a tree is, simply put, a knapsack problem combined with tree DP.
Example: Luogu P2014 CTSC1997 Course Selection
There are \(n\) courses. Course \(i\) is worth \(a_i\) credits, and every course has zero or one prerequisite. A course with a prerequisite can be taken only after the prerequisite has been completed.
A student is going to take \(m\) courses. Find the maximum number of credits the student can earn.
\(n,m \leq 300\)
Each course has at most one prerequisite, just as each node of a rooted tree has at most one parent.
This suggests building a tree from that property, so that the courses form a forest. For convenience, add a course worth \(0\) credits (number it \(0\)) and make it the prerequisite of every course that has none. The forest then becomes a tree rooted at course \(0\).
Let \(f(u,i,j)\) be the maximum number of credits in the subtree rooted at node \(u\) when the first \(i\) subtrees of \(u\) have been traversed and \(j\) courses have been chosen.
The transition combines features of tree DP and knapsack DP: enumerate every child \(v\) of \(u\) and, together with it, the number of courses chosen in the subtree rooted at \(v\), and merge the result of that subtree into \(u\).
Let \(s_x\) be the number of children of node \(x\) and \(\textit{siz}_x\) the size of the subtree rooted at \(x\). This gives the recurrence:
Note the constraints in the recurrence above: they make sure that certain meaningless states are never visited.
The second dimension of \(f\) is easy to drop with a rolling array. If you do so, enumerate \(j\) in decreasing order.
It can be shown that this approach runs in \(O(nm)\) time1.
Reference code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | |
Practice problems
Rerooting DP
Rerooting DP, a kind of tree DP, is also known as the two-pass scan. The problem usually does not specify a root, and changing the root affects certain values, such as the sum of the depths of the child nodes or the sum of the vertex weights.
It usually takes two DFS passes. The first precomputes information such as depths and sums of vertex weights; the second runs the rerooting dynamic programming.
We now work through some example problems to get familiar with it.
Example: [POI2008] STA-Station
Given a tree with \(n\) nodes, find a node such that the sum of the depths of all nodes is largest when the tree is rooted at that node.
Let \(u\) be the current node and \(v\) a child of the current node. First, let \(s_i\) be the number of nodes in the subtree rooted at \(i\); then \(s_u=1+\sum s_v\). Computing all the \(s_i\) clearly takes one DFS. This DFS is the preprocessing: it gives the number of nodes in every subtree when the tree is rooted at some particular node.
Now for the state transition, which is where the rerooting comes in. Let \(f_u\) be the sum of the depths of all nodes when the tree is rooted at \(u\).
\(f_v\leftarrow f_u\) expresses the rerooting: we move from the tree rooted at \(u\) to the tree rooted at \(v\). Clearly, in this transition, rooting the tree at \(v\) instead of \(u\) changes the depths of the nodes in their subtrees. Specifically:
-
The depth of every node in the subtree of \(v\) decreases by one, so the total depth decreases by \(s_v\).
-
The depth of every node outside the subtree of \(v\) increases by one, so the total depth increases by \(n-s_v\).
These two facts give the recurrence \(f_v = f_u - s_v + n - s_v=f_u + n - 2 \times s_v\).
So the second DFS traverses the whole tree and applies the transition \(f_v=f_u + n - 2 \times s_v\), which yields the sum of depths for every choice of root. One final pass over the sums of depths of all the roots gives the answer.
Reference code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 | |
Practice problems
References and notes
This page is an unofficial English translation of the original OI Wiki page (revision 9bb3a8e6), machine-translated by Claude Fable 5.2 on 2026-11-16. It has been modified from the original by translation and may contain errors. It is not endorsed by OI Wiki.
Found a translation problem? Report it on GitHub.
Authors of the original page: aaron20100919, Ir1d, StudyingFather, 24OI-bot, greyqz, billchenchina, ouuan, Henry-ZHR, H-J-Granger, sshwy, ShaoChenHeng, Early0v0, ShizuhaAki, Enter-tainer, isdanni, thredreams, Xeonacid, qz-cqy, kenlig, ksyx, NachtgeistW, Marcythm, widsnoy, lychees, Tiphereth-A, amakerlife, c-forrest, hhc0001 (full contribution history)
All content on this page is provided under the terms of CC BY-SA 4.0 and SATA; additional terms may apply.