"Minimum Cost Walk in Weighted Graph Using Bitwise AND and Disjoint Set Union (DSU)"
IntuitionThe problem involves finding the minimum cost of a walk between two nodes in an undirected weighted graph, where the cost is defined as the bitwise AND
# Intuition
The problem involves finding the minimum cost of a walk between two nodes in an undirected weighted graph, where the cost is defined as the bitwise AND of the weights of the edges traversed during the walk. To solve this, we need to determine if there is a path between the two nodes and compute the minimum bitwise AND value along that path.

# Approach
1. Disjoint Set Union (DSU) Data Structure:
- We use a DSU (also known as Union-Find) to manage the connected components of the graph.
- Each node initially belongs to its own set.
- We union sets based on the edges provided, ensuring that we keep track of the bitwise AND value for each set.

2. Union by Rank:
- When uniting two sets, we use the rank to decide which set becomes the parent. This helps keep the tree balanced, ensuring efficient operations.
- During the union operation, we update the bitwise AND value for the new parent by taking the bitwise AND of the current value and the new edge weight.

3. Query Processing:
- For each query, we check if the two nodes belong to the same set using the findUPar function.
- If they are in the same set, we return the bitwise AND value for that set.
- If they are in different sets, we return -1, indicating no path exists between the nodes.
# Complexity
- Time complexity: O(n+m⋅α(n)+q⋅α(n)), where m is the number of edges, α(n) is the inverse Ackermann function and q is the number of queries.
- Space complexity: O(n)
# Code
```cpp []
class DisjointSet {
public: 
    vector<int> rank, parent, size, bitwiseAND; 
    DisjointSet(int n) {
        rank.resize(n+1, 0); 
        parent.resize(n+1);
        size.resize(n+1); 
        bitwiseAND.resize(n+1, INT_MAX); 
        for(int i = 0;i<=n;i++) {
            parent[i] = i; 
            size[i] = 1; 
        }
    }

    int findUPar(int node) {
        if(node == parent[node])
            return node; 
        return parent[node] = findUPar(parent[node]); 
    }

    void unionByRank(int u, int v, int w) {
        int ulp_u = findUPar(u); 
        int ulp_v = findUPar(v); 
        if(ulp_u == ulp_v) {
            bitwiseAND[ulp_u] &= w;
            return;
        }
        if(rank[ulp_u] < rank[ulp_v]) {
            parent[ulp_u] = ulp_v; 
            bitwiseAND[ulp_v] &= bitwiseAND[ulp_u] & w;
        }
        else if(rank[ulp_v] < rank[ulp_u]) {
            parent[ulp_v] = ulp_u; 
            bitwiseAND[ulp_u] &= bitwiseAND[ulp_v] & w;
        }
        else {
            parent[ulp_v] = ulp_u; 
            bitwiseAND[ulp_u] &= bitwiseAND[ulp_v] & w;
            rank[ulp_u]++; 
        }
    }

    void unionBySize(int u, int v) {
        int ulp_u = findUPar(u); 
        int ulp_v = findUPar(v); 
        if(ulp_u == ulp_v) return; 
        if(size[ulp_u] < size[ulp_v]) {
            parent[ulp_u] = ulp_v; 
            size[ulp_v] += size[ulp_u]; 
        }
        else {
            parent[ulp_v] = ulp_u;
            size[ulp_u] += size[ulp_v]; 
        }
    }
}; 

class Solution {
public:
    vector<int> minimumCost(int n, vector<vector<int>>& edges, vector<vector<int>>& query) {
        DisjointSet ds(n);
        for(int i=0; i<edges.size(); i++){
            int u = edges[i][0], v = edges[i][1], w = edges[i][2];
            ds.unionByRank(u, v, w);
        }
        vector<int> ans;
        for(int i=0; i<query.size(); i++){
            int u = query[i][0], v = query[i][1];
            if(ds.findUPar(u) != ds.findUPar(v)) {ans.push_back(-1);}
            else{
                ans.push_back(ds.bitwiseAND[ds.findUPar(u)]);
            }
        }
        return ans;
    }
};
```
['C++']