Problem 18: Maximum Independent Set in a Tree

Problem Statement: Given a tree, find the size of the maximum independent set using tree DP.

Input

The first line contains n, the number of nodes. Next n-1 lines contain two integers u and v representing an edge.

Output

Print the size of the maximum independent set.

Examples


Input:
5
1 2
1 3
3 4
3 5

Output:
3

Solution Explanation

Method 1: Use tree DP where for each node you calculate two values: one when the node is included and one when it is excluded. Method 2: Use recursion to explore subsets of nodes, but the DP approach is more efficient and avoids recomputation.

Solution in C++


#include 
#include 
#include 
using namespace std;

int n;
vector> adj;
vector> dp;

void dfs(int u, int p){
    dp[u][0] = 0; // exclude u
    dp[u][1] = 1; // include u
    for(auto v : adj[u]){
        if(v == p) continue;
        dfs(v, u);
        dp[u][0] += max(dp[v][0], dp[v][1]);
        dp[u][1] += dp[v][0];
    }
}

int main(){
    cin >> n;
    adj.resize(n+1);
    dp.assign(n+1, vector(2,0));
    for(int i=1;i> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1,-1);
    cout << max(dp[1][0], dp[1][1]);
    return 0;
}