Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

3079. Minimum Edge Weight Equilibrium Queries in a Tree

My accepted Python solution to LeetCode problem 3079, Minimum Edge Weight Equilibrium Queries in a Tree, running in 2189ms.

  • Difficulty: Hard
  • Python
  • Runtime 2189ms
  • Memory 32.6MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 2189ms, memory 32.6MB, accepted 2026-01-01.

python
class Solution:
    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:
        from collections import defaultdict
        
        # Build adjacency list
        graph = defaultdict(list)
        for u, v, w in edges:
            graph[u].append((v, w))
            graph[v].append((u, w))
        
        # Binary lifting for LCA
        LOG = 15
        parent = [[-1] * LOG for _ in range(n)]
        depth = [0] * n
        
        # cnt[node][w] = count of edge with weight w from root to node
        cnt = [[0] * 27 for _ in range(n)]
        
        # BFS to build parent and cnt arrays
        from collections import deque
        visited = [False] * n
        queue = deque([0])
        visited[0] = True
        
        while queue:
            node = queue.popleft()
            for neighbor, weight in graph[node]:
                if not visited[neighbor]:
                    visited[neighbor] = True
                    depth[neighbor] = depth[node] + 1
                    parent[neighbor][0] = node
                    
                    # Copy parent's counts and add current edge
                    for w in range(1, 27):
                        cnt[neighbor][w] = cnt[node][w]
                    cnt[neighbor][weight] += 1
                    
                    queue.append(neighbor)
        
        # Fill in ancestor table
        for j in range(1, LOG):
            for i in range(n):
                if parent[i][j-1] != -1:
                    parent[i][j] = parent[parent[i][j-1]][j-1]
        
        def lca(u, v):
            if depth[u] < depth[v]:
                u, v = v, u
            
            diff = depth[u] - depth[v]
            for j in range(LOG):
                if (diff >> j) & 1:
                    u = parent[u][j]
            
            if u == v:
                return u
            
            for j in range(LOG - 1, -1, -1):
                if parent[u][j] != parent[v][j]:
                    u = parent[u][j]
                    v = parent[v][j]
            
            return parent[u][0]
        
        result = []
        for a, b in queries:
            l = lca(a, b)
            path_len = depth[a] + depth[b] - 2 * depth[l]
            
            # Count edge weights on path
            max_count = 0
            for w in range(1, 27):
                count_on_path = cnt[a][w] + cnt[b][w] - 2 * cnt[l][w]
                max_count = max(max_count, count_on_path)
            
            result.append(path_len - max_count)
        
        return result

Source