Watch 7 video solutions for Minimum Edge Weight Equilibrium Queries in a Tree, a hard level problem involving Array, Tree, Graph. This walkthrough by codingMohan has 2,415 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
There is an undirected tree with n nodes labeled from 0 to n - 1. You are given the integer n and a 2D integer array edges of length n - 1, where edges[i] = [ui, vi, wi] indicates that there is an edge between nodes ui and vi with weight wi in the tree.
You are also given a 2D integer array queries of length m, where queries[i] = [ai, bi]. For each query, find the minimum number of operations required to make the weight of every edge on the path from ai to bi equal. In one operation, you can choose any edge of the tree and change its weight to any value.
Note that:
ai to bi is a sequence of distinct nodes starting with node ai and ending with node bi such that every two adjacent nodes in the sequence share an edge in the tree.Return an array answer of length m where answer[i] is the answer to the ith query.
Example 1:
Input: 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]] Output: [0,0,1,3] Explanation: In the first query, all the edges in the path from 0 to 3 have a weight of 1. Hence, the answer is 0. In the second query, all the edges in the path from 3 to 6 have a weight of 2. Hence, the answer is 0. In the third query, we change the weight of edge [2,3] to 2. After this operation, all the edges in the path from 2 to 6 have a weight of 2. Hence, the answer is 1. In the fourth query, we change the weights of edges [0,1], [1,2] and [2,3] to 2. After these operations, all the edges in the path from 0 to 6 have a weight of 2. Hence, the answer is 3. For each queries[i], it can be shown that answer[i] is the minimum number of operations needed to equalize all the edge weights in the path from ai to bi.
Example 2:
Input: n = 8, edges = [[1,2,6],[1,3,4],[2,4,6],[2,5,3],[3,6,6],[3,0,8],[7,0,2]], queries = [[4,6],[0,4],[6,5],[7,4]] Output: [1,2,2,3] Explanation: In the first query, we change the weight of edge [1,3] to 6. After this operation, all the edges in the path from 4 to 6 have a weight of 6. Hence, the answer is 1. In the second query, we change the weight of edges [0,3] and [3,1] to 6. After these operations, all the edges in the path from 0 to 4 have a weight of 6. Hence, the answer is 2. In the third query, we change the weight of edges [1,3] and [5,2] to 6. After these operations, all the edges in the path from 6 to 5 have a weight of 6. Hence, the answer is 2. In the fourth query, we change the weights of edges [0,7], [0,3] and [1,3] to 6. After these operations, all the edges in the path from 7 to 4 have a weight of 6. Hence, the answer is 3. For each queries[i], it can be shown that answer[i] is the minimum number of operations needed to equalize all the edge weights in the path from ai to bi.
Constraints:
1 <= n <= 104edges.length == n - 1edges[i].length == 30 <= ui, vi < n1 <= wi <= 26edges represents a valid tree.1 <= queries.length == m <= 2 * 104queries[i].length == 20 <= ai, bi < nProblem Overview: You are given a weighted tree and multiple queries. Each query asks for the minimum number of edge weight changes required so that all edges along the path between two nodes have the same weight. The key observation is that the optimal strategy keeps the most frequent weight on that path and changes the rest.
Approach 1: DFS for Path Finding and Frequency Analysis (O(q * n) time, O(n) space)
For each query, run a DFS or BFS to find the path between the two nodes. While traversing, maintain a frequency counter of the edge weights encountered. After reaching the destination, compute the path length and subtract the highest frequency weight on that path. That difference equals the number of operations required. This approach directly simulates the query but recomputes paths repeatedly, which becomes expensive when the number of queries is large.
Approach 2: LCA with Prefix Weight Frequencies (O((n + q) log n) time, O(n * W) space)
Preprocess the tree using a depth-first traversal and compute binary lifting tables for LCA queries. During the DFS, maintain prefix frequency counts for each possible edge weight from the root to every node. For a query (u, v), compute their LCA. The frequency of each weight on the path is derived from prefix arrays: freq[u] + freq[v] - 2 * freq[lca]. The path length is known from node depths, and the minimum operations equal pathLength - maxWeightFrequency. This avoids recomputing paths and makes each query efficient.
This method combines classic tree traversal with graph preprocessing and prefix counting stored in arrays. The core improvement comes from converting repeated path exploration into constant-time frequency reconstruction after an LCA lookup.
Recommended for interviews: Start with the DFS path approach to show you understand the problem and the key observation about keeping the most frequent weight. Then move to the LCA + prefix frequency technique. Interviewers expect this optimization because it reduces repeated work across queries and demonstrates strong understanding of tree preprocessing and query optimization.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS Path Search with Frequency Counting | O(q * n) | O(n) | Small trees or very few queries where recomputing paths is acceptable |
| LCA with Prefix Weight Frequencies | O((n + q) log n) | O(n * W) | Large trees and many queries; optimal approach for competitive programming and interviews |