Use all edges inside a component | DSU  briefly explained| python
Approach\nThe $AND$ operation is an operation that can only decrease or keep equal, i.e., $x \& y \leq x$ and $x \& y \leq y$. Applying the AND operation with t
# Approach\nThe $AND$ operation is an operation that can only decrease or keep equal, i.e., $x \\& y \\leq x$ and $x \\& y \\leq y$. Applying the AND operation with the elements of some array will at most equal the minimum number. In a random distribution of many elements, it tends to $0$, as there is a low probability that all the elements have the same bit set to $1$. Thus, to minimize the cost, it\'s optimal to use as many elements as possible (all). In this problem, we aim to use all edges of the graph since there are no restrictions on repeating nodes or edges.\n\nHowever, the answer will not be exactly the AND value of all edges, as the graph may not be connected. So, there are two problems to solve: getting the $AND$ of the edges inside a specific connected component and determining if two nodes are connected. Otherwise, we cannot construct a walk, and the answer will be $0$.\n\n- To address the first problem, we can run a Depth-First Search (DFS) or Breadth-First Search (BFS) and keep track of all the edges used, then calculate the AND with all of them. \n\n- For the second problem, running a DFS for each pair in the queries is quite expensive ($n^2$). Instead, we can use a classic data structure known as the Disjoint Set Union (DSU), which efficiently answers the question "Given $u$ and $v$, are $u$ and $v$ connected?" The DSU\'s operation can be efficiently answered in $O(\\alpha(n))$ time complexity using path compression and union by size. This is the inverse ackerman function that grows very slow, actually is basically constant for the limits of the problem.\n\nWe can also calculate the $AND$ of the component by modifying the DSU structure. We keep track of the current AND for the component, which at the beginning can be $2^{30} - 1$, a number with all ones in the first $29$ bits. When uniting some nodes, we update the AND value as $AND[u] = AND[u] \\& AND[v] \\& w$, which means that the AND of the component to which $u$ belongs is equal to the AND of the component of $v$ AND the edge that will connect both components. We need to perform this operation even if $u$ and $v$ are already in the same component.\n\n## A brief explanation of DSU\nThe idea of DSU is to build a set of trees, where each element belongs to exactly one tree. For any given node, we can find the root of the tree to which it belongs, and nodes in the same tree share the same root. But to achieve such good complexity two optimizations are needed: path compression and union by size.\n\nThe DSU structure need two operation \n- findRoot: Get the root of the three in which $u$ belongs\n- union: Union the threes of the nodes $u,v$ \n \nWhit those operation we can know if two nodes are in the same component just checking $findRoot(u) == findRoot(v)$.\n\nBoth operations need to apply the optimizations, path compression for $findRoot$ and join by size for the $unite$ function\n\n### Path compression\nInitially, we define an array $parent$ such that $parent[i] = i$. With path compression, at the end, $parent_i$ will represent the root of the  that $i$ belongs to. When finding the root of the current tree/component, we traverse the tree upwards through the parent relationship until we reach the root i.e the node in which $parent[u] = u$. During this traversal, we update the parent of all nodes visited to the root, effectively compressing the path. This optimization speeds up subsequent find operations.\n\nYou can see here, imagine that we have a tree rooted in $9$, and we want to unite the node $11$ with $6$. We need to update the parent for $11$, so we traverse the tree over the parents until we reach the root $9$ node visiting the nodes $6,7,8,9$ But instead of just return the node in the root we also set the parent of all nodes that we visited to $9$.\n\n![image.png](https://assets.leetcode.com/users/images/f84b52e7-d85b-4477-b989-ed03cc55321c_1712461508.3154647.png)\n\n> Actually, at the time of joining $11$ with $6$, the node $6$ had already passed through the process of compressing the root, so it would jump directly to the root $9$ instead of $7$ and return faster. This is one of the reasons why DSU is so fast.\n\n\n### Union by size\nThis optimization decides how to unite two trees. It chooses to unite the tree with smaller size to the tree with larger size. This decision minimizes the number of updates required for parent pointers, as the smaller tree becomes a subtree of the larger tree so only its nodes should update their parents at some point in the future and it is better to update less *(This is similar to joining two sets, we go through the small one adding its elements to the larger one).*\n\n## Complexity\n- $O(n+m)$ DSU operations are amortized to basically constant. \n$m$ is the length of the edges, since it is a graph is limited to $n\\times (n+1) / 2$ and in this problem also $m\\leq 10^5$\n\n# Code\n```python\nclass Solution:\n    def minimumCost(self, n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:\n        \n        # DSU Structure\n        parent = [i for i in range(n)]\n        size = [1]*n\n        AND = [(1<<(31))-1]*n\n        \n        def root(u):\n            if u == parent[u]:\n                return u\n            parent[u] = root(parent[u])\n            return parent[u]\n        \n        def union_by_size(u,v,w):\n            \n            u = root(u)\n            v = root(v)\n            \n            if u == v:\n                AND[u]&=w\n                return\n            \n            if size[u]<size[v]:\n                (u,v) = (v,u)\n                \n            size[u]+=size[v]\n            parent[v] = u \n            AND[u]=AND[u]&AND[v]&w\n        # End of DSU\n            \n        for u,v,w in edges:\n            union_by_size(u,v,w)\n            \n        ans = []\n        for u,v in query: \n            if u == v: \n                ans.append(0)\n            elif root(u) == root(v):\n                ans.append(AND[root(u)])\n            else: \n                ans.append(-1)\n                \n        return ans
['Python3']