🔥 Optimized Union-Find with Bitwise AND Aggregation 🔥 || ~10ms in Rust & Go
💡 Intuition
The key observation is that the minimum bitwise AND of a walk between two nodes is determined by the AND aggregation of all edges in their connected
# 💡 Intuition

- The key observation is that the minimum bitwise AND of a walk between two nodes is determined by the __AND aggregation of all edges in their <ins>connected component</ins>__. You can clear see it in example graph image. 
![graphviz.png](https://assets.leetcode.com/users/images/e639cfc0-1d49-4a30-aee0-3c4a177f49d4_1742476373.1736739.png)
- We use __<ins>Union-Find</ins>__ (_Disjoint Set Union_) with path compression and union by size to efficiently process connected components. 


# ⚡ Approach

1. __Initialize DSU:__ Each node is its own parent, with 
$min\_and = -1$.
2. __Process edges:__ Union nodes and update $min\_and$ in the root.
3. __Process queries:__ If two nodes __share the same $root$__, return $min\_and[root]$; otherwise, return $-1$

# Complexity
- __⏳ Time Complexity__: $O((E + Q) α(N))$
    - Find (path compression): $O(α(N))$ (_inverse Ackermann, nearly constant_)
    - Union (by size): $O(α(N))$
    - Processing edges & queries: $O(E·α(N) + Q·α(N))$
    
- __💾 Space Complexity__: $O(N)$
    - Linear sizes for parent, size, and min_and arrays.

# Code
```rust []
struct UnionFind {
    parent: Vec<usize>,
    size: Vec<usize>,
    min_and: Vec<i32>,
}

impl Solution {
    pub fn minimum_cost(n: i32, edges: Vec<Vec<i32>>, query: Vec<Vec<i32>>) -> Vec<i32> {
        let n = n as usize;
        let mut uf = UnionFind::new(n);

        // Process edges to construct the Union-Find structure
        for edge in &edges {
            let (u, v, w) = (edge[0] as usize, edge[1] as usize, edge[2]);
            uf.union(u, v, w);
        }

        // Process queries efficiently
        query.iter().map(|q| {
                let (s, t) = (uf.find(q[0] as usize), uf.find(q[1] as usize));
                if s == t { uf.min_and[s] } else { -1 }
            }).collect()
    }
}

impl UnionFind {
    fn new(n: usize) -> Self {
        UnionFind {
            parent: (0..n).collect(),
            size: vec![1; n],
            min_and: vec![-1; n],
        }
    }

    fn find(&mut self, x: usize) -> usize {
        if self.parent[x] != x {
            self.parent[x] = self.find(self.parent[x]); // Path compression
        }
        self.parent[x]
    }

    fn union(&mut self, a: usize, b: usize, weight: i32) {
        let mut root_a = self.find(a);
        let mut root_b = self.find(b);

        if root_a != root_b {
            // Union by size: attach the smaller tree under the larger tree
            if self.size[root_a] < self.size[root_b] {
                std::mem::swap(&mut root_a, &mut root_b);
            }
            self.parent[root_b] = root_a;
            self.size[root_a] += self.size[root_b];
            self.min_and[root_a] &= self.min_and[root_b];
        }

        // Update min_and for the new root
        self.min_and[root_a] &= weight;
    }
}
```
``` golang []
type UnionFind struct {
	size   []int  // Stores the size of each component
	parent []int  // Stores the parent of each node
	minAND []int  // Stores the minimum AND cost for each component
}

// minimumCost finds the minimum AND-cost walk for each query.
func minimumCost(n int, edges [][]int, queries [][]int) []int {
	// Initialize Union-Find data structure
	uf := &UnionFind{
		size:   make([]int, n),
		parent: make([]int, n),
		minAND: make([]int, n),
	}

	// Each node starts as its own parent, with size 1 and minAND -1 (for bitwise AND operations)
	for i := 0; i < n; i++ {
		uf.size[i] = 1
		uf.parent[i] = i
		uf.minAND[i] = -1
	}

	// Union nodes based on edges
	for _, edge := range edges {
		u, v, weight := edge[0], edge[1], edge[2]
		root := uf.Union(u, v)
		uf.minAND[root] &= weight
	}

	// Process queries
	result := make([]int, len(queries))
	for i, q := range queries {
		s, t := uf.Find(q[0]), uf.Find(q[1])
		if s != t {
			result[i] = -1
		} else {
			result[i] = uf.minAND[s]
		}
	}

	return result
}

// Find returns the root representative of a node, applying path compression.
func (uf *UnionFind) Find(node int) int {
	if uf.parent[node] != node {
		uf.parent[node] = uf.Find(uf.parent[node]) // Path compression
	}
	return uf.parent[node]
}

// Union merges two sets and returns the new root.
func (uf *UnionFind) Union(a, b int) int {
	rootA, rootB := uf.Find(a), uf.Find(b)

	if rootA != rootB {
		// Union by size: attach the smaller tree under the larger tree
		if uf.size[rootA] < uf.size[rootB] {
			rootA, rootB = rootB, rootA
		}
		uf.size[rootA] += uf.size[rootB]
		uf.minAND[rootA] &= uf.minAND[rootB]
		uf.parent[rootB] = rootA
	}
	return rootA
}
```
['Bit Manipulation', 'Union Find', 'Go', 'Rust']