3812. Minimum Edge Toggles on a Tree

You are given an undirected tree with n nodes, numbered from 0 to n - 1. It is represented by a 2D integer array edges​​​​​​​ of length n - 1, where edges[i] = [a_i, b_i] indicates that there is an edge between nodes a_i and b_i in the tree.

You are also given two binary strings start and target of length n. For each node x, start[x] is its initial color and target[x] is its desired color.

In one operation, you may pick an edge with index i and toggleboth of its endpoints. That is, if the edge is [u, v], then the colors of nodes u and v each flip from '0' to '1' or from '1' to '0'.

Return an array of edge indices whose operations transform start into target. Among all valid sequences with minimum possible length, return the edge indices in increasing​​​​​​​ order.

If it is impossible to transform start into target, return an array containing a single element equal to -1.

class Solution {
    int dfs(vector<vector<pair<int,int>>>& adj, int u, int par, vector<int>& res, string& s, string& t) {
        int sub = s[u] != t[u];
        for (auto [v, idx] : adj[u]) {
            if (v == par) continue;
            int child = dfs(adj, v, u, res, s, t);
            if (child) res.push_back(idx);
            sub ^= child;
        }
        return sub;
    }

public:
    vector<int> minimumFlips(int n, vector<vector<int>>& edges, string start, string target) {
        if((count(begin(start),end(start),'0') + count(begin(target),end(target),'0')) & 1) return {-1};
        vector<vector<pair<int,int>>> adj(n);
        for (int i = 0; i < edges.size(); i++) {
            int u = edges[i][0], v = edges[i][1];
            adj[u].push_back({v, i});
            adj[v].push_back({u, i});
        }
        vector<int> res;
        dfs(adj,0, -1,res,start,target);
        sort(res.begin(), res.end());
        return res;
    }
};