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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Edge Weight Equilibrium Queries in a Tree

Number: 3079

Difficulty: Hard

Paid? No

Companies: Sprinklr

Problem Description

Given an undirected tree with n nodes (labeled from 0 to n - 1) and n - 1 weighted edges, answer m independent queries. For each query, you are given two nodes a and b. The goal is to determine the minimum number of operations needed to make the weight of every edge in the unique simple path from a to b equal. In one operation, you may choose any edge in the tree and change its weight to any value.

Key Insights

  • The unique path between two nodes can be found by computing their Lowest Common Ancestor (LCA) and then tracing both nodes up to the LCA.
  • For the edges on the path, count the frequency of each weight.
  • The best strategy is to change all edges to the weight that occurs most frequently on that path.
  • The minimum operations required is (total number of edges on the path) minus (the frequency of the most common weight).
  • Preprocessing the tree (using DFS/BFS) to record parent pointers and depths can help efficiently compute paths and answer queries.

Space and Time Complexity

Time Complexity: O(m * L) per worst-case query where L is the length of the path (plus O(n) preprocessing). In many cases, L is much shorter than n. Space Complexity: O(n) for storing the tree and auxiliary data (parent, depth arrays).

Solution

The solution involves a two-step process. First, preprocess the tree using depth-first search (DFS) from an arbitrary root (e.g. node 0) to compute parent information, depth, and the edge weight that connects each node to its parent. Then, for each query, use the LCA approach: lift both query nodes until they converge to a common ancestor, all the while collecting the weights of the edges encountered. By counting how many times each weight appears along the path, we determine the optimal weight target; the answer is the number of edges on the path minus the count of the most frequent weight.

The key data structures used are:

  • An adjacency list for representing the tree.
  • Arrays (or hash maps in some languages) for keeping track of parent, depth, and the edge weight from the parent.
  • A frequency counter for the weights along each query path.

This approach ensures that we only change the minimum necessary edges; note that each query is independent and the tree resets to its initial state after every query.

Code Solutions

# Python solution

from collections import defaultdict, Counter
import sys
sys.setrecursionlimit(10**5)

def minOperations(n, edges, queries):
    # Build adjacency list: each node -> list of (next_node, weight)
    tree = defaultdict(list)
    for u, v, w in edges:
        tree[u].append((v, w))
        tree[v].append((u, w))
    
    # Preprocessing: DFS to set parent, depth, and edge weight to parent
    parent = [-1] * n
    depth = [0] * n
    parentEdgeWeight = [-1] * n  # weight from node to its parent
    
    def dfs(node, par):
        for next_node, w in tree[node]:
            if next_node == par:
                continue
            parent[next_node] = node
            depth[next_node] = depth[node] + 1
            parentEdgeWeight[next_node] = w
            dfs(next_node, node)
    
    dfs(0, -1)
    
    def getPathWeights(u, v):
        # Collect weights along path from u to v (inclusive of the edges connecting u to v)
        weights = []
        # Bring u and v to the same depth
        while depth[u] > depth[v]:
            weights.append(parentEdgeWeight[u])
            u = parent[u]
        while depth[v] > depth[u]:
            weights.append(parentEdgeWeight[v])
            v = parent[v]
        # Move both up until they meet at LCA
        while u != v:
            weights.append(parentEdgeWeight[u])
            weights.append(parentEdgeWeight[v])
            u = parent[u]
            v = parent[v]
        return weights

    results = []
    for a, b in queries:
        # Get all weights along path from a to b
        pathWeights = getPathWeights(a, b)
        if not pathWeights:
            results.append(0)
        else:
            freq = Counter(pathWeights)
            max_freq = max(freq.values())
            # number of operations is total edges - frequency of most common weight
            results.append(len(pathWeights) - max_freq)
    return results

# Example usage:
n = 7
edges = [[0,1,1],[1,2,1],[2,3,1],[3,4,2],[4,5,2],[5,6,2]]
queries = [[0,3],[3,6],[2,6],[0,6]]
print(minOperations(n, edges, queries))  # Expected output: [0, 0, 1, 3]
← Back to All Questions