2445. Number of Nodes With Value One

There is an undirected connected tree with n nodes labeled from 1 to n and n - 1 edges. You are given the integer n. The parent node of a node with a label v is the node with the label floor (v / 2). The root of the tree is the node with the label 1.

• For example, if n = 7, then the node with the label 3 has the node with the label floor(3 / 2) = 1 as its parent, and the node with the label 7 has the node with the label floor(7 / 2) = 3 as its parent.

You are also given an integer array queries. Initially, every node has a value 0 on it. For each query queries[i], you should flip all values in the subtree of the node with the label queries[i].

Return the total number of nodes with the value 1 after processing all the queries.

Note that:

• Flipping the value of a node means that the node with the value 0 becomes 1 and vice versa.
• floor(x) is equivalent to rounding x down to the nearest integer.

class Solution {
    int dfs(int u, int ma, unordered_set<int>& us, bool fl) {
        if(u > ma) return 0;
        if(us.count(u)) fl = !fl;
        int res = fl;
        res += dfs(u * 2, ma, us, fl);
        res += dfs(u * 2 + 1, ma, us, fl);
        return res;
    }
public:
    int numberOfNodes(int n, vector<int>& Q) {
        unordered_set<int> us;
        for(auto q : Q) {
            if(us.count(q)) us.erase(q);
            else us.insert(q);
        }
        return dfs(1,n,us,false);
    }
};