CSES 1130 - DP on Tree solution

CSES1130.cpp

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

// dp[i][0] = max matching if we don't take edge (i, i_children)
// dp[i][1] = max matching if we take edge (i, i_children)
ll dp[(size_t)2e5 + 1][2];

void dfs(vector<vector<ll>> &tree, ll root, ll parent){
    // run 2 loop since dp[i][1] value depend on dp[i][0] value
    // dp[x][0] = 0 when x is bottom leaf parent
    // dp[x][1] = 1 when x is bottom leaf parent, dp[i][1] is not guarentee to be greater than 0
    for(ll i : tree[root]){ // don't take (root, i) => we can take or not take (i, i_children)
        if(i == parent) continue; // i_parent is not in i_children
        dfs(tree, i, root); // calculate max matching for all children
        dp[root][0] += max(dp[i][0], dp[i][1]);
    }
    for(ll i : tree[root]){ // take (root, i) => we cannot take (i, i_children)
        if(i == parent) continue; // i_parent is not in i_children
        // dp[i][0] + 1: plus 1 because we take (root, i) (or (i_parent, i))
        // dp[root][0] - max(dp[i][0], dp[i][1]): max matching when we take (root, root_children) without i in root_children
        dp[root][1] = max(dp[root][1], dp[i][0] + 1 + dp[root][0] - max(dp[i][0], dp[i][1]));
    }
}

int main(){
    ll n;
    cin >> n;
    vector<vector<ll>> tree(n + 1);
    n--;
    while(n--){
        ll a, b;
        cin >> a >> b;
        tree[a].push_back(b);
        tree[b].push_back(a);
    }
    dfs(tree, 1, -1);
    cout << max(dp[1][0], dp[1][1]);
}