We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Edge Weight Equilibrium Queries in a Tree

Difficulty: Hard

Problem Description

Given an undirected tree with n nodes and a list of edges representing the tree structure, determine the minimum number of operations required to equalize the weights of the edges along the path between two specified nodes for multiple queries. Each operation allows changing the weight of an edge to any value.

Key Insights

  • The problem involves working with a tree structure where each edge has a weight.
  • Each query is independent, meaning the tree returns to its initial state after each query.
  • The goal is to find the minimum number of changes needed to make all weights equal on the path between two nodes.
  • The weights of edges range from 1 to 26, which allows for counting occurrences of weights along paths efficiently.

Space and Time Complexity

Time Complexity: O(n + m * log(m)) - where n is the number of edges and m is the number of queries, considering path compression and traversal. Space Complexity: O(n) - for storing the tree structure and auxiliary data structures.

Solution

To solve this problem, we can represent the tree using an adjacency list. For each query, we need to find the path between the two nodes and count the occurrences of each edge weight along that path. The steps are as follows:

  1. Build a graph using an adjacency list to represent the tree.
  2. For each query:
    • Use Depth First Search (DFS) or Breadth First Search (BFS) to find the path between the two nodes.
    • Count the occurrences of each edge weight in the path.
    • Determine the maximum frequency of any weight in the path.
    • The minimum operations needed will be the total number of edges in the path minus the maximum frequency.

This approach ensures that we efficiently retrieve the necessary edge weights and compute the result for each query.

Code Solutions

def min_operations(n, edges, queries):
    from collections import defaultdict, deque

    # Build the graph
    graph = defaultdict(list)
    for u, v, w in edges:
        graph[u].append((v, w))
        graph[v].append((u, w))

    def bfs(start, end):
        queue = deque([start])
        parent = {start: None}
        weights = {}
        while queue:
            node = queue.popleft()
            if node == end:
                break
            for neighbor, weight in graph[node]:
                if neighbor not in parent:  # unvisited
                    parent[neighbor] = node
                    weights[neighbor] = weight
                    queue.append(neighbor)

        # reconstruct the path
        path_weights = []
        current = end
        while current is not None:
            if parent[current] is not None:
                path_weights.append(weights[current])
            current = parent[current]
        return path_weights

    results = []
    for a, b in queries:
        path_weights = bfs(a, b)
        count = defaultdict(int)
        
        for weight in path_weights:
            count[weight] += 1
        
        max_freq = max(count.values(), default=0)
        results.append(len(path_weights) - max_freq)

    return results
← Back to All Questions