C++ || Java || Python || Bitwise AND + DSU = Magic! || Min-Cost Walk Solution!
IntuitionThe problem involves finding the minimum cost of a walk between given nodes in an undirected weighted graph. The cost of a walk is determined by the bi
# Intuition
The problem involves finding the minimum cost of a walk between given nodes in an undirected weighted graph. The cost of a walk is determined by the bitwise AND of the weights of the edges traversed.

A direct approach using BFS/DFS to compute the AND for each possible path is infeasible due to large constraints. Instead, we can use Disjoint Set Union (DSU) with an additional array to store the minimum AND value for each connected component. This allows efficient querying in constant time.



# Approach
1. Use DSU to group connected components:

   - We'll use union by rank and path compression to efficiently merge nodes.
   - Each component will store the AND of all edge weights connecting its nodes.

2. Processing edges:

   - For each edge (u, v, w), we merge u and v in the DSU.
   - Update the AND value of the connected component.

3. Answering queries efficiently:

   - If si and ti belong to different components, return -1 (no walk exists).
   - Otherwise, return the AND value stored for the component.

This allows processing m queries in O(1) each after an initial O(n log n) preprocessing step.
# Complexity
- Time complexity:
1. Building DSU: 𝑂(𝑛)
2. Merging Edges: O(nlogn) (Amortized over all union operations)
3. Processing Queries: O(1) per query
4. Total Complexity: O(nlogn+m)


- Space complexity: 
1. O(n) (for DSU structures)

# Code
```cpp []
struct DSU {
    int n, set_size;
    vector<int> parent, rank;
    vector<int> ands;

    // Constructor to initialize DSU with n elements
    DSU(int a) : n(a), set_size(a), parent(a + 1), ands(a + 1, -1), rank(a + 1, 1) {
        for (int i = 1; i <= n; i++) parent[i] = i; // Initially, each node is its own parent
    }

    // Find function with path compression
    int find(int x) {
        if (x != parent[x])
            return parent[x] = find(parent[x]); // Path compression for efficiency
        return x;
    }

    // Merge two components and update the AND values
    void merge(int x, int y, int wt) {
        int xroot = find(x), yroot = find(y);
        if (xroot != yroot) { // If they belong to different components
            // Union by rank: Attach smaller tree to larger tree
            if (rank[xroot] >= rank[yroot]) {
                parent[yroot] = xroot; 
                rank[xroot] += rank[yroot];
            } else {
                parent[xroot] = yroot; 
                rank[yroot] += rank[xroot];
            }
            set_size--;

            // Updating the AND values for the merged component
            if (ands[xroot] == -1 && ands[yroot] == -1) {
                ands[xroot] = wt;
                ands[yroot] = wt;
            } else {
                if (ands[xroot] != -1 && ands[yroot] != -1) {
                    int toand = ands[xroot] & ands[yroot];
                    ands[xroot] = toand & wt;
                    ands[yroot] = toand & wt;
                } else if (ands[xroot] == -1) {
                    int toand = ands[yroot];
                    ands[xroot] = toand & wt;
                    ands[yroot] = toand & wt;
                } else {
                    int toand = ands[xroot];
                    ands[xroot] = toand & wt;
                    ands[yroot] = toand & wt;
                }
            }
        } else {
            // If already in the same set, update the AND value
            ands[xroot] &= wt;
        }
    }

    // Solution function to return the AND value if nodes belong to the same component, else -1
    int solution(int x, int y) {
        int xroot = find(x);
        int yroot = find(y);
        if (xroot != yroot) {
            return -1;
        } else {
            return ands[xroot];
        }
    }

    // Reset function to restore DSU to its initial state
    void reset() { 
        set_size = n; 
        for (int i = 1; i <= n; i++) parent[i] = i, rank[i] = 1; 
    }

    // Function to return the number of connected components
    int size() { 
        return set_size; 
    }

    // Debugging function to print DSU parent relationships
    void print() { 
        for (int i = 1; i <= n; i++) 
            cout << i << " -> " << parent[i] << '\n'; 
    }
};

class Solution {
public:
    vector<int> minimumCost(int n, vector<vector<int>>& edges, vector<vector<int>>& query) {
        DSU dsu(n);
        
        // Process each edge and merge into the DSU
        for (auto &it : edges) {
            dsu.merge(it[0], it[1], it[2]);
        }

        vector<int> ans;
        // Answer each query using DSU's solution function
        for (auto &it : query) {
            int u = it[0];
            int v = it[1];
            ans.push_back(dsu.solution(u, v));
        }
        return ans;
    }
};

```

```java []
class DSU {
    int[] parent, rank, ands;
    int set_size;

    // Constructor initializes DSU
    DSU(int n) {
        parent = new int[n];
        rank = new int[n];
        ands = new int[n];
        set_size = n;

        for (int i = 0; i < n; i++) {
            parent[i] = i; // Initially, each node is its own parent
            rank[i] = 1;
            ands[i] = -1; // -1 indicates no AND value calculated yet
        }
    }

    // Find function with path compression
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    // Merging two components and updating the AND values
    void merge(int x, int y, int wt) {
        int xroot = find(x), yroot = find(y);
        if (xroot != yroot) {
            // Union by rank
            if (rank[xroot] >= rank[yroot]) {
                parent[yroot] = xroot;
                rank[xroot] += rank[yroot];
            } else {
                parent[xroot] = yroot;
                rank[yroot] += rank[xroot];
            }
            set_size--;

            // Updating the AND values of the component
            int toand = (ands[xroot] != -1 ? ands[xroot] : ands[yroot]);
            ands[xroot] = ands[yroot] = (toand == -1) ? wt : (toand & wt);
        } else {
            ands[xroot] &= wt; // Update the existing AND value
        }
    }

    // Returns the AND value for connected components, otherwise -1
    int solution(int x, int y) {
        return (find(x) == find(y)) ? ands[find(x)] : -1;
    }
}

class Solution {
    public int[] minimumCost(int n, int[][] edges, int[][] query) {
        DSU dsu = new DSU(n);

        // Merge all edges into DSU
        for (int[] edge : edges) {
            dsu.merge(edge[0], edge[1], edge[2]);
        }

        int[] ans = new int[query.length];
        // Answer each query
        for (int i = 0; i < query.length; i++) {
            ans[i] = dsu.solution(query[i][0], query[i][1]);
        }
        return ans;
    }
}

```

``` python []
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))  # Each node is its own parent
        self.rank = [1] * n  # Rank array for union by rank
        self.ands = [-1] * n  # Stores the AND values for each component

    def find(self, x):
        """Find function with path compression"""
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def merge(self, x, y, wt):
        """Merging two components and updating the AND values"""
        xroot, yroot = self.find(x), self.find(y)
        if xroot != yroot:
            # Union by rank
            if self.rank[xroot] >= self.rank[yroot]:
                self.parent[yroot] = xroot
                self.rank[xroot] += self.rank[yroot]
            else:
                self.parent[xroot] = yroot
                self.rank[yroot] += self.rank[xroot]

            # Updating the AND values of the component
            toand = self.ands[xroot] if self.ands[xroot] != -1 else self.ands[yroot]
            self.ands[xroot] = self.ands[yroot] = wt if toand == -1 else (toand & wt)
        else:
            self.ands[xroot] &= wt  # Update the existing AND value

    def solution(self, x, y):
        """Returns the AND value for connected components, otherwise -1"""
        return self.ands[self.find(x)] if self.find(x) == self.find(y) else -1

class Solution:
    def minimumCost(self, n, edges, query):
        dsu = DSU(n)
        for u, v, w in edges:
            dsu.merge(u, v, w)
        return [dsu.solution(u, v) for u, v in query]

```
['Bit Manipulation', 'Union Find', 'C++', 'Java', 'Python3']