C++ Solution | Modified DSU | Disjoint Set Union | Bit Manipulation | Graph | Dynamic Programming
Approach
Modified DSU
Bit Manipulation
Dynamic Programming
Shortest Path
Bit Mask
Graph
Complexity
Time complexity: O(n + e + q)
Space complexity: O(n)
Code
# Approach
- Modified DSU
- Bit Manipulation 
- Dynamic Programming
- Shortest Path
- Bit Mask
- Graph

# Complexity
- Time complexity: O(n + e + q)
- Space complexity: O(n)

# Code
```cpp []
class ModifiedDSU {
    private:
        int * weight;
        int * size;
        int * parent;
        const int MAX_COST = (1 << 17) - 1;

    public:
        ModifiedDSU(int n){
            size = (int *) malloc(n * sizeof(int));
            parent = (int *) malloc(n * sizeof(int));
            weight = (int *) malloc(n * sizeof(int));
            for(int i=0; i<n; i++){
                size[i] = 1;
                parent[i] = i;
                weight[i] = MAX_COST;
            }
        }

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

        void unionBySize(int u, int v, int w){
            int uPar = findParent(u);
            int vPar = findParent(v);
            weight[uPar] &= w;
            weight[vPar] &= w;
            if(uPar == vPar) return;
            if(size[uPar] < size[vPar]){
                parent[uPar] = vPar;
                size[vPar] += size[uPar];
                weight[vPar] &= weight[uPar];
            }
            else{
                parent[vPar] = uPar;
                size[uPar] += size[vPar];
                weight[uPar] &= weight[vPar];
            }
        }

        int getWeight(int node){
            return weight[node];
        }

        ~ModifiedDSU(){
            free(weight);
            free(size);
            free(parent);
        }
};


class Solution {
public:
    vector<int> minimumCost(int n, vector<vector<int>>& edges, vector<vector<int>>& query) {
        ModifiedDSU dsu(n);
        for(vector<int> & edge : edges){
            dsu.unionBySize(edge[0], edge[1], edge[2]);
        }
        int qSize = query.size();
        vector<int> res(qSize);
        for(int i=0; i<qSize; i++){
            int uPar = dsu.findParent(query[i][0]);
            int vPar = dsu.findParent(query[i][1]);
            if(uPar != vPar){
                res[i] = -1;
            }
            else{
                res[i] = dsu.getWeight(uPar);
            }
        }
        return res;
    }
};
```
['Array', 'Math', 'Dynamic Programming', 'Bit Manipulation', 'Depth-First Search', 'Union Find', 'Graph', 'Shortest Path', 'Strongly Connected Component', 'C++']