Even Tree

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

c++

vector<int> adj[101];
bool dfs(int u, int par, int& res) {
    bool even = false;
    for(auto& v : adj[u]) {
        if(v == par) continue;
        if(dfs(v, u, res)) res++;
        else even = !even;
    }
    return even;
}

int evenForest(int v, int e, vector<int> t, vector<int> f) {
    for(int i = 1; i <= v; i++) adj[i].clear();
    for(int i = 0; i < e; i++) {
        adj[t[i]].push_back(f[i]);
        adj[f[i]].push_back(t[i]);
    }
    int res = 0;
    dfs(1, -1, res);
    return res;
}