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\n1 2\n1 3\n3 4\n3 5

Output:
3

Solution in C++


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n;
vector<vector<int>> adj;
vector<vector<int>> 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<int>(2,0));
    for(int i=1;i<n;i++){
        int u,v; cin >> 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;
}