Minimum Edge Weight Equilibrium Queries in a Tree — Solution
Minimum Edge Weight Equilibrium Queries in a Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Minimum Edge Weight Equilibrium Queries in a Tree is a hard coding problem on arrays, trees and graph, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Trees, Graph
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
An undirected tree has n nodes numbered 0 to n - 1. Each edges[i] = [u, v, w] is an edge between u and v with weight w, where 1 <= w <= 26.
For each query queries[j] = [a, b], find the minimum number of operations needed to make every edge on the path from a to b have the same weight. One operation changes the weight of one edge to any value.
Queries are independent: the tree returns to its original weights before each query. Return an array whose j-th entry answers queries[j].
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: Path 2 → 6 has weights 1, 2, 2, 2: change the single 1. Path 0 → 6 has three 1s and three 2s: change three edges.
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: Path 4 → 6 is 4–2–1–3–6 with weights 6, 6, 4, 6: change the 4.
Example 3
Input: n = 1, edges = [], queries = [[0,0]]
Output: [0]
Explanation: An empty path needs no changes.
Constraints
1 <= n <= 10^4edges.length == n - 1edges[i].length == 30 <= u, v < n1 <= w <= 26edges represents a valid tree1 <= queries.length <= 2 * 10^4queries[j].length == 20 <= a, b < n
Hints for Minimum Edge Weight Equilibrium Queries in a Tree
Hint 1
For one path, keep the most common weight and change everything else: the answer is
path length − (count of the most frequent weight).Hint 2
There are only 26 possible weights. Root the tree and store, for every node, how many edges of each weight lie on its path from the root.
Hint 3
With
l = LCA(a, b), the count of weightwon the path iscnt[a][w] + cnt[b][w] − 2·cnt[l][w], and the length isdepth[a] + depth[b] − 2·depth[l]. Find the LCA with binary lifting.
How to solve Minimum Edge Weight Equilibrium Queries in a Tree
The cheapest way to equalise a path is to keep its most frequent weight. Because weights come from just 26 values, per-node prefix counts from the root let any path's weight histogram be assembled from three nodes: the two endpoints and their lowest common ancestor.
Approach
- BFS from node 0 to get each node's parent, depth and
cnt[v][w]— the number of edges of weightwbetween the root andv(the parent's counts plus the edge intov). - Build binary-lifting tables
up[k][v](the2^k-th ancestor). - For a query, lift the deeper endpoint to the other's depth, then lift both while their ancestors differ to find
l. - Path length
len = depth[a] + depth[b] − 2·depth[l]; best kept weightm = max_w (cnt[a][w] + cnt[b][w] − 2·cnt[l][w]); answerlen − m.
Why it works
The root-to-a and root-to-b paths both contain the root-to-l path; subtracting it twice leaves exactly the edges of the a–b path, so the histogram is exact. Changing every edge that differs from the kept weight is necessary and sufficient, and keeping the most frequent weight minimises the number of changes.
Complexity
- Time —
O((n + q) · (26 + log n)) - Space —
O(n · (26 + log n))
Pitfalls
- When
a == bthe path is empty and the answer is 0. - Weights are 1-based (1 to 26); size the count table accordingly.
- Per-query path walking is
O(n)each — too slow for2 · 10^4queries on a long path; that is why the LCA is needed.
Reference solution
Python
from typing import List
def minOperationsQueries(n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:
adj = [[] for _ in range(n)]
for u, v, w in edges:
adj[u].append((v, w))
adj[v].append((u, w))
LOG = max(1, n.bit_length())
up = [[0] * n for _ in range(LOG)]
depth = [0] * n
cnt = [[0] * 27 for _ in range(n)]
seen = [False] * n
seen[0] = True
order = [0]
for u in order:
for v, w in adj[u]:
if not seen[v]:
seen[v] = True
up[0][v] = u
depth[v] = depth[u] + 1
cnt[v] = cnt[u][:]
cnt[v][w] += 1
order.append(v)
for k in range(1, LOG):
prev, cur = up[k - 1], up[k]
for v in range(n):
cur[v] = prev[prev[v]]
def lca(a, b):
if depth[a] < depth[b]:
a, b = b, a
diff = depth[a] - depth[b]
for k in range(LOG):
if diff >> k & 1:
a = up[k][a]
if a == b:
return a
for k in range(LOG - 1, -1, -1):
if up[k][a] != up[k][b]:
a, b = up[k][a], up[k][b]
return up[0][a]
res = []
for a, b in queries:
l = lca(a, b)
length = depth[a] + depth[b] - 2 * depth[l]
keep = max(cnt[a][w] + cnt[b][w] - 2 * cnt[l][w] for w in range(1, 27))
res.append(length - keep)
return resJava
public static int[] minOperationsQueries(int n, int[][] edges, int[][] queries) {
List<List<int[]>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] e : edges) { adj.get(e[0]).add(new int[]{e[1], e[2]}); adj.get(e[1]).add(new int[]{e[0], e[2]}); }
int LOG = 1;
while ((1 << LOG) <= n) LOG++;
int[][] up = new int[LOG][n];
int[] depth = new int[n];
int[][] cnt = new int[n][27];
boolean[] seen = new boolean[n];
int[] order = new int[n];
int head = 0, tail = 0;
order[tail++] = 0;
seen[0] = true;
while (head < tail) {
int u = order[head++];
for (int[] e : adj.get(u)) {
int v = e[0];
if (seen[v]) continue;
seen[v] = true;
up[0][v] = u;
depth[v] = depth[u] + 1;
cnt[v] = cnt[u].clone();
cnt[v][e[1]]++;
order[tail++] = v;
}
}
for (int k = 1; k < LOG; k++) for (int v = 0; v < n; v++) up[k][v] = up[k - 1][up[k - 1][v]];
int[] res = new int[queries.length];
for (int q = 0; q < queries.length; q++) {
int a = queries[q][0], b = queries[q][1];
int x = a, y = b;
if (depth[x] < depth[y]) { int t = x; x = y; y = t; }
int diff = depth[x] - depth[y];
for (int k = 0; k < LOG; k++) if (((diff >> k) & 1) == 1) x = up[k][x];
if (x != y) {
for (int k = LOG - 1; k >= 0; k--) if (up[k][x] != up[k][y]) { x = up[k][x]; y = up[k][y]; }
x = up[0][x];
}
int l = x, keep = 0;
for (int w = 1; w <= 26; w++) keep = Math.max(keep, cnt[a][w] + cnt[b][w] - 2 * cnt[l][w]);
res[q] = depth[a] + depth[b] - 2 * depth[l] - keep;
}
return res;
}C++
vector<int> minOperationsQueries(int n, vector<vector<int>>& edges, vector<vector<int>>& queries) {
vector<vector<pair<int, int>>> adj(n);
for (auto& e : edges) { adj[e[0]].push_back({e[1], e[2]}); adj[e[1]].push_back({e[0], e[2]}); }
int LOG = 1;
while ((1 << LOG) <= n) LOG++;
vector<vector<int>> up(LOG, vector<int>(n, 0));
vector<int> depth(n, 0);
vector<array<int, 27>> cnt(n);
cnt[0].fill(0);
vector<bool> seen(n, false);
vector<int> order = {0};
seen[0] = true;
for (size_t h = 0; h < order.size(); h++) {
int u = order[h];
for (auto& e : adj[u]) {
int v = e.first, w = e.second;
if (seen[v]) continue;
seen[v] = true;
up[0][v] = u;
depth[v] = depth[u] + 1;
cnt[v] = cnt[u];
cnt[v][w]++;
order.push_back(v);
}
}
for (int k = 1; k < LOG; k++) for (int v = 0; v < n; v++) up[k][v] = up[k - 1][up[k - 1][v]];
vector<int> res;
for (auto& q : queries) {
int a = q[0], b = q[1], x = a, y = b;
if (depth[x] < depth[y]) swap(x, y);
int diff = depth[x] - depth[y];
for (int k = 0; k < LOG; k++) if ((diff >> k) & 1) x = up[k][x];
if (x != y) {
for (int k = LOG - 1; k >= 0; k--) if (up[k][x] != up[k][y]) { x = up[k][x]; y = up[k][y]; }
x = up[0][x];
}
int l = x, keep = 0;
for (int w = 1; w <= 26; w++) keep = max(keep, cnt[a][w] + cnt[b][w] - 2 * cnt[l][w]);
res.push_back(depth[a] + depth[b] - 2 * depth[l] - keep);
}
return res;
}JavaScript
var minOperationsQueries = function(n, edges, queries) {
var adj = [];
for (var i = 0; i < n; i++) adj.push([]);
for (var e = 0; e < edges.length; e++) {
adj[edges[e][0]].push(edges[e][1], edges[e][2]);
adj[edges[e][1]].push(edges[e][0], edges[e][2]);
}
var LOG = 1;
while ((1 << LOG) <= n) LOG++;
var up = [], depth = new Array(n), cnt = new Array(n * 27), seen = new Array(n);
for (var k = 0; k < LOG; k++) { up.push(new Array(n)); for (var z = 0; z < n; z++) up[k][z] = 0; }
for (var a0 = 0; a0 < n; a0++) { depth[a0] = 0; seen[a0] = false; }
for (var c0 = 0; c0 < n * 27; c0++) cnt[c0] = 0;
seen[0] = true;
var order = [0];
for (var h = 0; h < order.length; h++) {
var u = order[h];
for (var j = 0; j < adj[u].length; j += 2) {
var v = adj[u][j], w = adj[u][j + 1];
if (seen[v]) continue;
seen[v] = true;
up[0][v] = u;
depth[v] = depth[u] + 1;
for (var t = 0; t < 27; t++) cnt[v * 27 + t] = cnt[u * 27 + t];
cnt[v * 27 + w]++;
order.push(v);
}
}
for (var k2 = 1; k2 < LOG; k2++) for (var x = 0; x < n; x++) up[k2][x] = up[k2 - 1][up[k2 - 1][x]];
var lca = function(a, b) {
if (depth[a] < depth[b]) { var tmp = a; a = b; b = tmp; }
var diff = depth[a] - depth[b];
for (var k = 0; k < LOG; k++) if ((diff >> k) & 1) a = up[k][a];
if (a === b) return a;
for (var k3 = LOG - 1; k3 >= 0; k3--) if (up[k3][a] !== up[k3][b]) { a = up[k3][a]; b = up[k3][b]; }
return up[0][a];
};
var res = [];
for (var q = 0; q < queries.length; q++) {
var p = queries[q][0], r = queries[q][1], l = lca(p, r);
var len = depth[p] + depth[r] - 2 * depth[l], keep = 0;
for (var wt = 1; wt <= 26; wt++) {
var c = cnt[p * 27 + wt] + cnt[r * 27 + wt] - 2 * cnt[l * 27 + wt];
if (c > keep) keep = c;
}
res.push(len - keep);
}
return res;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Binary Trees and Tree Traversals