Minimum edge weight equilibrium queries in a tree

Array Tree Graph Theory Strongly Connected Component

45.5% acceptance

Feb 25, 2026

358

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 where answer[i] is the answer to the ith query.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn min_operations_queries(n: i32, edges: Vec<Vec<i32>>, queries: Vec<Vec<i32>>) -> Vec<i32> {
    let n = n as usize;
    let mut adj: Vec<Vec<(usize, usize)>> = vec![vec![]; n];
    for e in &edges {
      let (u, v, w) = (e[0] as usize, e[1] as usize, e[2] as usize);
      adj[u].push((v, w)); adj[v].push((u, w));
    }
    let log = 14usize;
    let mut depth = vec![0usize; n];
    let mut parent = vec![vec![0usize; n]; log];
    let mut cnt = vec![vec![0usize; n]; 27]; // cnt[w][node] = count of weight-w edges from root to node
    // BFS from root 0
    let mut order = Vec::with_capacity(n);
    let mut visited = vec![false; n];
    let mut queue = std::collections::VecDeque::new();
    queue.push_back(0usize); visited[0] = true;
    while let Some(u) = queue.pop_front() {
      order.push(u);
      for &(v, w) in &adj[u] {
        if !visited[v] {
          visited[v] = true;
          depth[v] = depth[u] + 1;
          parent[0][v] = u;
          for ww in 1..=26 { cnt[ww][v] = cnt[ww][u]; }
          cnt[w][v] += 1;
          queue.push_back(v);
        }
      }
    }
    for bit in 1..log {
      for u in 0..n { parent[bit][u] = parent[bit-1][parent[bit-1][u]]; }
    }
    let lca = |mut a: usize, mut b: usize| -> usize {
      if depth[a] < depth[b] { std::mem::swap(&mut a, &mut b); }
      let diff = depth[a] - depth[b];
      for bit in 0..log { if (diff >> bit) & 1 == 1 { a = parent[bit][a]; } }
      if a == b { return a; }
      for bit in (0..log).rev() { if parent[bit][a] != parent[bit][b] { a = parent[bit][a]; b = parent[bit][b]; } }
      parent[0][a]
    };
    queries.iter().map(|q| {
      let (a, b) = (q[0] as usize, q[1] as usize);
      let l = lca(a, b);
      let total_edges = (depth[a] + depth[b] - 2 * depth[l]) as i32;
      let max_w_count = (1..=26).map(|w| (cnt[w][a] + cnt[w][b] - 2 * cnt[w][l]) as i32).max().unwrap_or(0);
      total_edges - max_w_count
    }).collect()
  }
}