Tree Dynamic Programming

Tree DP combines independent child-subtree decisions once a root-side condition is fixed. We compute maximum independent-set size and minimum vertex-cover size on an unweighted tree, demonstrating complementary objectives with different state meanings. The existing Trees folder remains unchanged; here the focus is why the parent-choice state makes child combinations sufficient.

Prerequisites: Tree Representation; Tree Dynamic Programming in Trees; parent traversal. Related existing lessons: Tree Dynamic Programming.

Build the idea

1. Recognize the repeated subproblems

   Choosing arbitrary vertex subsets is exponential. Removing a tree edge separates two subproblems, so child subtrees interact only through their shared parent. A chosen/not-chosen condition at the parent captures that boundary. The absence of cycles is essential:cross edges between child regions would invalidate independent combination without more state.

2. Define the state

   For independent set, take[u] is maximum selected count in u’s rooted subtree when u is selected; skip[u] is the maximum when u is not. For vertex cover, coverIn[u] and coverOut[u] are minimum counts under the analogous condition. These are exact subtree optima, not global values for every root. All vertex costs are one in this program.

3. Derive the transition

   If an independent-set parent is taken, each child must be skipped; otherwise each child may choose its better state. Thus take=1+Σskip and skip=Σmax(take, skip). For cover, a taken parent already covers its child edges, so choose min per child; an omitted parent forces every child taken. The objective operation reverses from max to min while the edge constraint remains explicit.

   $$\mathrm{take}\left[u\right]=1+\Sigma \mathrm{skip}\left[\mathrm{child}\right];\mathrm{skip}\left[u\right]=\Sigma \max \left(\mathrm{take}\right[\mathrm{child}],\mathrm{skip}[\mathrm{child}\left]\right)$$

4. Base cases and computation order

   Root at vertex 1 and build an iterative parent-before-child traversal order, skipping each vertex’s parent in adjacency scans. Reverse that order for bottom-up evaluation. Leaves start with take=coverIn=1 and skip=coverOut=0. At the root, take the better of its two states for each objective. Iteration avoids stack overflow on a long chain.

5. Correctness and invariant

   Induct on subtree size. Once u’s inclusion status is fixed, the edge rules impose exactly the child-state restrictions stated, and distinct child subtrees share no other vertices or edges. Their optimum contributions can therefore be summed independently. The complement of an independent set is a vertex cover, so maximum independent size plus minimum cover size equals n, a useful cross-check.

6. Work the example

   In a star with center 1 and leaves 2…5, each leaf has independent states (1,0) and cover states (1,0). The center has independent take=1, skip=4, and cover in=1, out=4. Print 4 1:all leaves form a maximum independent set, and the center is a minimum cover.

   vertex class	MIS take	MIS skip	cover in	cover out
   leaf	1	0	1	0
   center	1	4	1	4

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

#include<iostream>
#include<vector>
#include<algorithm>
int main(){
    int n;
    std::cin>>n;
    std::vector<std::vector<int>>tree(n+1);
    for(int i=1;i<n;++i){
        int u,v;
        std::cin>>u>>v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    std::vector<int>parent(n+1),order{1};
    for(int i=0;i<(int)order.size();++i){
        int u=order[i];
        for(int v:tree[u]){
            if(v!=parent[u]){
                parent[v]=u;
                order.push_back(v);
            }
        }
    }
    std::vector<int>take(n+1,1),skip(n+1),coverIn(n+1,1),coverOut(n+1);
    for(int i=n-1;i>=0;--i){
        int u=order[i];
        for(int v:tree[u]){
            if(parent[v]==u){
                take[u]+=skip[v];
                skip[u]+=std::max(take[v],skip[v]);
                coverIn[u]+=std::min(coverIn[v],coverOut[v]);
                coverOut[u]+=coverIn[v];
            }
        }
    } // Reversed parent-before-child order is bottom-up.
    std::cout<<std::max(take[1],skip[1])<<' '<<std::min(coverIn[1],coverOut[1])<<'\n';
}

Complexity analysis

Two states per vertex for each objective, constant work per parent-child edge:O(n) time and O(n) adjacency/traversal/state space. No recursion-depth dependence. Counts are≤n and fit int; weighted variants often require long long.

Example input and output

Read n (1..200000), then n−1 edges of a valid connected unweighted tree, vertices 1..n. Print maximum independent-set size and minimum vertex-cover size.

Input

5
1 2
1 3
1 4
1 5

Output

4 1

In a star with center 1 and leaves 2…5, each leaf has independent states (1,0) and cover states (1,0). The center has independent take=1, skip=4, and cover in=1, out=4. Print 4 1:all leaves form a maximum independent set, and the center is a minimum cover.

Practical applications

Use subtree DP when a small boundary state separates child decisions. Tree vertex cover also has a leaf greedy solution for unit costs; DP generalizes more naturally to weights and richer local constraints. Rerooting adds parent-side contributions for every root.

Check your understanding

Why can child contributions be added independently?

Put it into practice

Enumerate all vertex subsets for a small tree and check both objectives.