Efficient Graph Queries Using DSU with Bitwise AND for Minimum Cost
IntuitionThis problem involves finding the minimum cost to connect two nodes in a graph, where the cost is determined using the bitwise AND (&) operation on edg
# Intuition
This problem involves finding the minimum cost to connect two nodes in a graph, where the cost is determined using the bitwise AND (&) operation on edge weights. We need to efficiently answer multiple queries about connectivity and cost.

Key Observations
Graph Representation:
The graph consists of n nodes and weighted edges.
We need to find the minimum cost path between two nodes using bitwise AND.
Using Disjoint Set Union (DSU)

Instead of maintaining an explicit graph, we use DSU (Union-Find) to track connected components.
The bitwise AND of all edge weights in a connected component determines the minimum cost.
Handling Queries Efficiently

If two nodes belong to different components, return -1.
Otherwise, return the stored minimum cost for that component.

# Approach
1. Implement Disjoint Set Union (DSU)
We create a DSU structure with:
parent[] → Tracks the ultimate parent (leader) of each node.
size[] → Stores the size of each component (for union by size).
cost[] → Stores the bitwise AND of all edge weights in the component.
2. Process Edges to Build the DSU
For each edge (u, v, wt), merge their sets using DSU:
Union by size to keep tree balanced.
Update the component cost using bitwise AND:
new cost=(cost of set 1)&(cost of set 2)&(new edge weight)
3. Answer Queries in Constant Time
For each query (u, v):
If Find(u) == Find(v), return cost[Find(u)].
Otherwise, return -1 (nodes are disconnected).

# Complexity
- Time complexity:
DSU Operations (Find & Union): 
O(α(n)) per operation (inverse Ackermann, almost constant).
Processing Edges: 
O(mα(n)) (where m is the number of edges).
Processing Queries: 
O(qα(n)) (where q is the number of queries).
Total Complexity: 
O((m+q)α(n)), which is nearly linear.

- Space complexity:
O(n)

# Code
```cpp []
class DisjointSet{
public:
    vector<int> parent,size,cost;
    DisjointSet(int n){
        parent.resize(n);
        size.resize(n,1);
        cost.resize(n,-1);
        for(int i=0;i<n;i++){
            parent[i] = i;
        }
    }
    int Find(int node){
        if(parent[node]==node)return node;
        return parent[node] = Find(parent[node]);
    }
    void Union(int u,int v,int wt){
        int ultPar_u = Find(u);
        int ultPar_v = Find(v);
        if(ultPar_u == ultPar_v){
            cost[ultPar_u] = cost[ultPar_u] & wt;
            return;
        }
        if(size[ultPar_u]<size[ultPar_v]){
            parent[ultPar_u] = ultPar_v;
            size[ultPar_v] += size[ultPar_u];
            cost[ultPar_v] = cost[ultPar_v] & wt;
            if(cost[ultPar_u]!=-1){
                cost[ultPar_v] = cost[ultPar_v] & cost[ultPar_u];
            }
        }else{
            parent[ultPar_v] = ultPar_u;
            size[ultPar_u] += size[ultPar_v];
            cost[ultPar_u] = cost[ultPar_u] & wt;
            if(cost[ultPar_v]!=-1){
                cost[ultPar_u] = cost[ultPar_u] & cost[ultPar_v];
            }
        }
    }
};
class Solution {
public:
    vector<int> minimumCost(int n, vector<vector<int>>& edges, vector<vector<int>>& query) {
        DisjointSet ds(n);
        for(auto edge : edges){
            int u = edge[0];
            int v = edge[1];
            int wt = edge[2];
            ds.Union(u,v,wt);
        }
        vector<int>ans;
        for(auto q : query){
            int u = q[0];
            int v = q[1];
            int ultPar_u = ds.Find(u);
            int ultPar_v = ds.Find(v);
            if(ultPar_u==ultPar_v){
                ans.push_back(ds.cost[ultPar_u]);
            }else{
                ans.push_back(-1);
            }
        }
        return ans;
    }
};
```
['C++']