Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
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 summary: 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: Queries are independent of each other, meaning that the tree returns to its initial state on each new query. The path from 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
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Tree
7 [[0,1,1],[1,2,1],[2,3,1],[3,4,2],[4,5,2],[5,6,2]] [[0,3],[3,6],[2,6],[0,6]]
8 [[1,2,6],[1,3,4],[2,4,6],[2,5,3],[3,6,6],[3,0,8],[7,0,2]] [[4,6],[0,4],[6,5],[7,4]]
kth-ancestor-of-a-tree-node)minimum-runes-to-add-to-cast-spell)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #2846: Minimum Edge Weight Equilibrium Queries in a Tree
class Solution {
public int[] minOperationsQueries(int n, int[][] edges, int[][] queries) {
int m = 32 - Integer.numberOfLeadingZeros(n);
List<int[]>[] g = new List[n];
Arrays.setAll(g, i -> new ArrayList<>());
int[][] f = new int[n][m];
int[] p = new int[n];
int[][] cnt = new int[n][0];
int[] depth = new int[n];
for (var e : edges) {
int u = e[0], v = e[1], w = e[2] - 1;
g[u].add(new int[] {v, w});
g[v].add(new int[] {u, w});
}
cnt[0] = new int[26];
Deque<Integer> q = new ArrayDeque<>();
q.offer(0);
while (!q.isEmpty()) {
int i = q.poll();
f[i][0] = p[i];
for (int j = 1; j < m; ++j) {
f[i][j] = f[f[i][j - 1]][j - 1];
}
for (var nxt : g[i]) {
int j = nxt[0], w = nxt[1];
if (j != p[i]) {
p[j] = i;
cnt[j] = cnt[i].clone();
cnt[j][w]++;
depth[j] = depth[i] + 1;
q.offer(j);
}
}
}
int k = queries.length;
int[] ans = new int[k];
for (int i = 0; i < k; ++i) {
int u = queries[i][0], v = queries[i][1];
int x = u, y = v;
if (depth[x] < depth[y]) {
int t = x;
x = y;
y = t;
}
for (int j = m - 1; j >= 0; --j) {
if (depth[x] - depth[y] >= (1 << j)) {
x = f[x][j];
}
}
for (int j = m - 1; j >= 0; --j) {
if (f[x][j] != f[y][j]) {
x = f[x][j];
y = f[y][j];
}
}
if (x != y) {
x = p[x];
}
int mx = 0;
for (int j = 0; j < 26; ++j) {
mx = Math.max(mx, cnt[u][j] + cnt[v][j] - 2 * cnt[x][j]);
}
ans[i] = depth[u] + depth[v] - 2 * depth[x] - mx;
}
return ans;
}
}
// Accepted solution for LeetCode #2846: Minimum Edge Weight Equilibrium Queries in a Tree
func minOperationsQueries(n int, edges [][]int, queries [][]int) []int {
m := bits.Len(uint(n))
g := make([][][2]int, n)
f := make([][]int, n)
for i := range f {
f[i] = make([]int, m)
}
p := make([]int, n)
cnt := make([][26]int, n)
cnt[0] = [26]int{}
depth := make([]int, n)
for _, e := range edges {
u, v, w := e[0], e[1], e[2]-1
g[u] = append(g[u], [2]int{v, w})
g[v] = append(g[v], [2]int{u, w})
}
q := []int{0}
for len(q) > 0 {
i := q[0]
q = q[1:]
f[i][0] = p[i]
for j := 1; j < m; j++ {
f[i][j] = f[f[i][j-1]][j-1]
}
for _, nxt := range g[i] {
j, w := nxt[0], nxt[1]
if j != p[i] {
p[j] = i
cnt[j] = [26]int{}
for k := 0; k < 26; k++ {
cnt[j][k] = cnt[i][k]
}
cnt[j][w]++
depth[j] = depth[i] + 1
q = append(q, j)
}
}
}
ans := make([]int, len(queries))
for i, qq := range queries {
u, v := qq[0], qq[1]
x, y := u, v
if depth[x] < depth[y] {
x, y = y, x
}
for j := m - 1; j >= 0; j-- {
if depth[x]-depth[y] >= (1 << j) {
x = f[x][j]
}
}
for j := m - 1; j >= 0; j-- {
if f[x][j] != f[y][j] {
x, y = f[x][j], f[y][j]
}
}
if x != y {
x = p[x]
}
mx := 0
for j := 0; j < 26; j++ {
mx = max(mx, cnt[u][j]+cnt[v][j]-2*cnt[x][j])
}
ans[i] = depth[u] + depth[v] - 2*depth[x] - mx
}
return ans
}
# Accepted solution for LeetCode #2846: Minimum Edge Weight Equilibrium Queries in a Tree
class Solution:
def minOperationsQueries(
self, n: int, edges: List[List[int]], queries: List[List[int]]
) -> List[int]:
m = n.bit_length()
g = [[] for _ in range(n)]
f = [[0] * m for _ in range(n)]
p = [0] * n
cnt = [None] * n
depth = [0] * n
for u, v, w in edges:
g[u].append((v, w - 1))
g[v].append((u, w - 1))
cnt[0] = [0] * 26
q = deque([0])
while q:
i = q.popleft()
f[i][0] = p[i]
for j in range(1, m):
f[i][j] = f[f[i][j - 1]][j - 1]
for j, w in g[i]:
if j != p[i]:
p[j] = i
cnt[j] = cnt[i][:]
cnt[j][w] += 1
depth[j] = depth[i] + 1
q.append(j)
ans = []
for u, v in queries:
x, y = u, v
if depth[x] < depth[y]:
x, y = y, x
for j in reversed(range(m)):
if depth[x] - depth[y] >= (1 << j):
x = f[x][j]
for j in reversed(range(m)):
if f[x][j] != f[y][j]:
x, y = f[x][j], f[y][j]
if x != y:
x = p[x]
mx = max(cnt[u][j] + cnt[v][j] - 2 * cnt[x][j] for j in range(26))
ans.append(depth[u] + depth[v] - 2 * depth[x] - mx)
return ans
// Accepted solution for LeetCode #2846: Minimum Edge Weight Equilibrium Queries in a Tree
/**
* [2846] Minimum Edge Weight Equilibrium Queries in a Tree
*/
pub struct Solution {}
// submission codes start here
use std::collections::HashMap;
struct UnionFind {
parents: Vec<usize>,
}
impl UnionFind {
fn new(n: usize) -> UnionFind {
let mut parents = Vec::with_capacity(n);
for i in 0..n {
parents.push(i);
}
UnionFind { parents }
}
fn find(&mut self, x: usize) -> usize {
if self.parents[x] == x {
return x;
}
self.parents[x] = self.find(self.parents[x]);
self.parents[x]
}
fn merge(&mut self, parent: usize, child: usize) {
self.parents[child] = parent;
}
}
struct Tree {
matrix: Vec<HashMap<usize, usize>>,
// 从节点0到节点i上权值为j边的个数
count: Vec<Vec<i32>>,
length: usize,
// tarjan算法辅助数组
least_common_ancestor: Vec<usize>,
// (i, x) 表示边，y 是least_common_ancestor的下标
query_edges: Vec<Vec<(usize, usize)>>,
uf: UnionFind,
visited: Vec<bool>,
}
impl Tree {
fn new(n: i32, edges: Vec<Vec<i32>>, queries: &Vec<Vec<i32>>) -> Tree {
let n = n as usize;
let mut matrix = Vec::with_capacity(n);
let mut count = Vec::with_capacity(n);
for _ in 0..=n {
matrix.push(HashMap::new());
count.push(vec![0; 27])
}
for edge in edges {
let x = edge[0] as usize;
let y = edge[1] as usize;
matrix[x].insert(y, edge[2] as usize);
matrix[y].insert(x, edge[2] as usize);
}
let mut tree = Tree {
matrix,
length: n,
count,
least_common_ancestor: vec![0; queries.len()],
query_edges: vec![vec![]; n],
uf: UnionFind::new(n),
visited: vec![false; n],
};
for (index, query) in queries.iter().enumerate() {
let x = query[0] as usize;
let y = query[1] as usize;
tree.query_edges[x].push((y, index));
tree.query_edges[y].push((x, index));
}
tree
}
fn tarjan(&mut self, node: usize, parent: usize) {
// 顺便构建count数组
if node != 0 {
self.count[node] = self.count[parent].clone();
self.count[node][self.matrix[node][&parent]] += 1;
}
let mut next_array = Vec::new();
for (next, _) in &self.matrix[node] {
if *next == parent {
continue;
}
next_array.push(*next);
}
for next in next_array {
self.tarjan(next, node);
self.uf.merge(node, next);
}
for (target, index) in &self.query_edges[node] {
if *target != node && !self.visited[*target] {
continue;
}
self.least_common_ancestor[*index] = self.uf.find(*target);
}
self.visited[node] = true;
}
}
impl Solution {
pub fn min_operations_queries(
n: i32,
edges: Vec<Vec<i32>>,
queries: Vec<Vec<i32>>,
) -> Vec<i32> {
let mut tree = Tree::new(n, edges, &queries);
tree.tarjan(0, 0);
let mut result = Vec::new();
for (index, query) in queries.iter().enumerate() {
let mut total = 0;
let mut max_count = 0;
let (x, y) = (query[0] as usize, query[1] as usize);
for i in 1..=26 {
let t = tree.count[x][i] + tree.count[y][i]
- 2 * tree.count[tree.least_common_ancestor[index]][i];
max_count = max_count.max(t);
total += t;
}
result.push(total - max_count);
}
result
}
}
// submission codes end
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_2846() {
assert_eq!(
Solution::min_operations_queries(
7,
vec![
vec![0, 1, 1],
vec![1, 2, 1],
vec![2, 3, 1],
vec![3, 4, 2],
vec![4, 5, 2],
vec![5, 6, 2]
],
vec![vec![0, 3], vec![3, 6], vec![2, 6], vec![0, 6]]
),
vec![0, 0, 1, 3]
)
}
}
// Accepted solution for LeetCode #2846: Minimum Edge Weight Equilibrium Queries in a Tree
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #2846: Minimum Edge Weight Equilibrium Queries in a Tree
// class Solution {
// public int[] minOperationsQueries(int n, int[][] edges, int[][] queries) {
// int m = 32 - Integer.numberOfLeadingZeros(n);
// List<int[]>[] g = new List[n];
// Arrays.setAll(g, i -> new ArrayList<>());
// int[][] f = new int[n][m];
// int[] p = new int[n];
// int[][] cnt = new int[n][0];
// int[] depth = new int[n];
// for (var e : edges) {
// int u = e[0], v = e[1], w = e[2] - 1;
// g[u].add(new int[] {v, w});
// g[v].add(new int[] {u, w});
// }
// cnt[0] = new int[26];
// Deque<Integer> q = new ArrayDeque<>();
// q.offer(0);
// while (!q.isEmpty()) {
// int i = q.poll();
// f[i][0] = p[i];
// for (int j = 1; j < m; ++j) {
// f[i][j] = f[f[i][j - 1]][j - 1];
// }
// for (var nxt : g[i]) {
// int j = nxt[0], w = nxt[1];
// if (j != p[i]) {
// p[j] = i;
// cnt[j] = cnt[i].clone();
// cnt[j][w]++;
// depth[j] = depth[i] + 1;
// q.offer(j);
// }
// }
// }
// int k = queries.length;
// int[] ans = new int[k];
// for (int i = 0; i < k; ++i) {
// int u = queries[i][0], v = queries[i][1];
// int x = u, y = v;
// if (depth[x] < depth[y]) {
// int t = x;
// x = y;
// y = t;
// }
// for (int j = m - 1; j >= 0; --j) {
// if (depth[x] - depth[y] >= (1 << j)) {
// x = f[x][j];
// }
// }
// for (int j = m - 1; j >= 0; --j) {
// if (f[x][j] != f[y][j]) {
// x = f[x][j];
// y = f[y][j];
// }
// }
// if (x != y) {
// x = p[x];
// }
// int mx = 0;
// for (int j = 0; j < 26; ++j) {
// mx = Math.max(mx, cnt[u][j] + cnt[v][j] - 2 * cnt[x][j]);
// }
// ans[i] = depth[u] + depth[v] - 2 * depth[x] - mx;
// }
// return ans;
// }
// }
Use this to step through a reusable interview workflow for this problem.
BFS with a queue visits every node exactly once — O(n) time. The queue may hold an entire level of the tree, which for a complete binary tree is up to n/2 nodes = O(n) space. This is optimal in time but costly in space for wide trees.
Every node is visited exactly once, giving O(n) time. Space depends on tree shape: O(h) for recursive DFS (stack depth = height h), or O(w) for BFS (queue width = widest level). For balanced trees h = log n; for skewed trees h = n.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Recursive traversal assumes children always exist.
Usually fails on: Leaf nodes throw errors or create wrong depth/path values.
Fix: Handle null/base cases before recursive transitions.