Maximum Edge Removal

• Time : $O(v + e)$
• Space : $O(v + e)$

int dfs(vector<vector<int>>& adj, int u, int par, int& res) {
    int now = 1;
    for(auto& v : adj[u]) {
        if(v == par) continue;
        int sub = dfs(adj,v,u,res);
        if(sub % 2 == 0) res += 1;
        else now += sub;
    }
    return now;
}

int Solution::solve(int A, vector<vector<int>> &B) {
    vector<vector<int>> adj(A + 1);
    for(auto b : B) {
        int u = b[0], v = b[1];
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    int res = 0;
    dfs(adj,1,-1,res);
    return res;
}