Let's analyze the problem step by step: --- ## Problem Restatement: - Graph \( G = (V, E) \) with weighted edges. - \( T \) is a Minimum Spanning Tree (MST) of \( G \). - A new weighted edge \( (u, v) \) is added to \( G \). - The goal: Determine the worst-case time complexity to check if \( T \) remains an MST after adding this edge. --- ## Key Points: - The graph is maintained with adjacency lists. - The initial MST \( T \) is known. - Adding an edge \( (u, v) \) may or may not alter the MST. - The check involves verifying if the MST is still optimal with the new edge. --- ## Approach: - After adding the edge, the main step is to determine whether the MST remains optimal. - This involves: 1. Finding the maximum weighted edge on the path between \( u \) and \( v \) in \( T \). 2. Comparing the weight of \( (u, v) \) with this maximum edge. - If \( (u, v) \) has a lower weight than the maximum edge on the path, replacing that edge can yield a better MST. - If not, the MST remains unchanged. --- ## Time Complexity: - Finding the path between \( u \) and \( v \) in a tree (since \( T \) is a tree) can be done using: - **LCA (Lowest Common Ancestor)** techniques with preprocessing for \( O(\log V) \) per query. - Or, simply, a DFS/BFS for each query, which in the worst case is \( O(V) \). - Since we only need to check one edge, and the worst-case scenario involves traversing the entire height of the tree, the complexity is dominated by the traversal. --- ## Conclusion: - The worst-case time complexity to check if \( T \) remains the MST after adding the edge is \( \Theta(\lvert V \rvert) \). --- ## Final Answer: **\(\boxed{\Theta(\lvert V \rvert)}\)** This matches the accepted answer.