Tree Dynamic Programming

Tree dynamic programming solves a global optimization or counting problem by combining answers for rooted subtrees. The essential question is what information a parent needs about a child. A subtree answer often needs several states because the best choice depends on what happens at its boundary. We will find a maximum independent set: a largest set of vertices with no edge joining two selected vertices. Trees make this manageable because, after fixing the choice at a vertex, its child subtrees have no edges between them.

Prerequisites: Rooted trees, postorder traversal, and basic dynamic programming.

Build the idea

1. 1. Root first, then define the states precisely. Choose vertex 1 as the root. Define take[v] as the largest independent-set size inside subtree(v) when v must be selected. Define skip[v] as the largest size when v must not be selected. These are constrained optima, not flags saying what a previous traversal happened to choose. A leaf has take=1 and skip=0. Storing only the unconstrained maximum loses the information needed to decide whether its parent may be chosen.
2. 2. Derive both transitions. If v is selected, every child must be skipped, so take[v]=1+sum(skip[c]). If v is skipped, each child can independently use its better state: skip[v]=sum(max(take[c],skip[c])). The final answer is max(take[1],skip[1]). The addition is valid because child subtrees are disjoint and have no cross edges. These facts fail in a general graph; simply running a DFS on a cyclic graph does not make the same recurrence correct.
3. 3. Calculate a concrete example. For edges 1–2, 1–3, 2–4, 2–5, the leaves 3,4,5 each have states (take,skip)=(1,0). Vertex 2 has take=1 and skip=2, because selecting both leaves beats selecting their parent. Vertex 1 has take=1+2+0=3 and skip=max(1,2)+max(1,0)=3. Both choices give an optimum of 3: {1,4,5} and {3,4,5} are examples. The DP deliberately keeps both alternatives instead of depending on an arbitrary tie-break.
4. 4. Process children before parents. First build parent pointers and an order in which every parent appears before its children. Walking that order backward ensures all child states are ready. Initialize take[v]=1 before accumulating contributions, and skip[v]=0. This is postorder computation without recursive calls. The code uses long long for state values so it can be adapted to weighted vertices, although int is enough for the unweighted answer, which never exceeds N.
5. 5. Prove the optimum by induction. The leaf states are exact. Assume the child states are exact. Any independent set containing v must skip each child, so it can contribute at most skip[c] from that child subtree; selecting each corresponding optimum reaches the bound. When v is excluded, either state is allowed for each child, and their independent optimum choices can coexist. Thus the transitions give exact constrained optima. Applying this argument upward proves the root answer is optimal.
6. 6. Recognize the reusable pattern. For weighted independent set, replace the initial 1 by weight[v]; if negative weights are allowed, skipping all vertices remains possible. For minimum vertex cover, choosing v permits either child state, while skipping v forces every child to be chosen, and maxima become minima. For reconstruction, start with the better root state and propagate the forced or optimal choices. Tree DP is a state-design technique, not one fixed recurrence; write the boundary meaning before writing code.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<vector<int>>g(n+1);
    for(int i=1,u,v;i<n;i++){
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<int>parent(n+1),order{1};
    // The order has each parent before its children.
    for(int i=0;i<(int)order.size();i++){
        int v=order[i];
        for(int u:g[v]){
            if(u!=parent[v]){
                parent[u]=v;
                order.push_back(u);
            }
        }
    }
    vector<long long>take(n+1,1),skip(n+1,0);
    for(int i=n-1;i>=0;i--){
        int v=order[i];
        for(int u:g[v]){
            if(parent[u]==v){
                // Selecting v forces its adjacent child u to be excluded.
                take[v]+=skip[u];
                // Skipping v lets each disjoint child subtree use its better state.
                skip[v]+=max(take[u],skip[u]);
            }
        }
    }
    cout<<max(take[1],skip[1])<<'\n';
}

Complexity analysis

O(N) time: each child contributes to two states once. O(N) auxiliary space for parents, traversal order, and the two DP arrays, in addition to O(N) adjacency storage.

Example input and output

N followed by N−1 tree edges. Output the maximum number of selected pairwise nonadjacent vertices.

Input

5
1 2
1 3
2 4
2 5

Output

3

The independent set {3,4,5} has three vertices, and the DP proves no valid set is larger.

Practical applications

Independent sets, weighted selections, vertex cover, tree matching, and counting valid colorings. Tree matching needs different states because a vertex can match at most one incident edge.

Check your understanding

If v is selected in an independent set, which state is allowed for each child?

Put it into practice

Extend the program to accept a weight for each vertex and maximize the sum of selected weights.