# Minimum Edge Weight Equilibrium Queries in a Tree
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-edge-weight-equilibrium-queries-in-a-tree)
Canonical: https://scaleengineer.com/dsa/problems/minimum-edge-weight-equilibrium-queries-in-a-tree
**Data structures:** Array, Tree, Graph
**Companies:** [Sprinklr](https://scaleengineer.com/companies/sprinklr)
---
## Problem
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._

**Example 1:**

![](https://assets.glich.co/dsa/minimum-edge-weight-equilibrium-queries-in-a-tree/image0.png) 

**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:**

![](https://assets.glich.co/dsa/minimum-edge-weight-equilibrium-queries-in-a-tree/image1.png) 

**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 <= 104`
* `edges.length == n - 1`
* `edges[i].length == 3`
* `0 <= ui, vi < n`
* `1 <= wi <= 26`
* The input is generated such that `edges` represents a valid tree.
* `1 <= queries.length == m <= 2 * 104`
* `queries[i].length == 2`
* `0 <= ai, bi < n`

# Approaches
## Brute Force Traversal for Each Query
This approach handles each query independently by performing a graph traversal to find the path between the two given nodes. For each query, it finds the path, collects the weights of all edges on that path, and then calculates the answer.
**Time:** O(M * N), where M is the number of queries and N is the number of nodes. For each of the M queries, we perform a traversal (BFS/DFS) which takes O(N) time in a tree. · **Space:** O(N), where N is the number of nodes. This is for storing the adjacency list, the parent array, and the queue for BFS for each query.
**Pros:** Simple to understand and implement.; Requires no complex data structures or algorithms beyond basic graph traversal.
**Cons:** Highly inefficient for a large number of queries.; The time complexity of O(M * N) is too slow for the given constraints and will likely result in a Time Limit Exceeded (TLE) error.
### Explanation
The core idea is to solve each query from scratch. Given a query with nodes `a` and `b`, we need to find the path connecting them. In a tree, this path is unique. We can use a graph traversal algorithm like Breadth-First Search (BFS) or Depth-First Search (DFS) to find this path. A straightforward way is to start a BFS from `a`, keeping track of the parent of each visited node. When we reach `b`, we can trace back the path to `a` using the parent pointers.

As we trace the path, we collect the weights of all its edges. We use a frequency map (or an array since weights are small) to count how many times each weight appears. The total number of edges on the path is also counted. To minimize the number of edge modifications, we should change all edge weights to match the most frequent weight on the path. If the most frequent weight appears `maxFreq` times and the total path length is `pathLength`, we need to change `pathLength - maxFreq` edges. This process is repeated for every single query.

```java
import java.util.*;

class Solution {
    public int[] minOperationsQueries(int n, int[][] edges, int[][] queries) {
        List<int[]>[] adj = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            adj[edge[0]].add(new int[]{edge[1], edge[2]});
            adj[edge[1]].add(new int[]{edge[0], edge[2]});
        }

        int[] result = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int u = queries[i][0];
            int v = queries[i][1];

            if (u == v) {
                result[i] = 0;
                continue;
            }

            // Find path from u to v using BFS
            int[] parent = new int[n];
            int[] edgeWeightToParent = new int[n];
            Arrays.fill(parent, -1);
            Queue<Integer> q = new LinkedList<>();
            
            q.offer(u);
            parent[u] = u; // Mark u as visited and its own parent

            while (!q.isEmpty()) {
                int curr = q.poll();
                if (curr == v) {
                    break;
                }
                for (int[] neighbor : adj[curr]) {
                    int nextNode = neighbor[0];
                    int weight = neighbor[1];
                    if (parent[nextNode] == -1) {
                        parent[nextNode] = curr;
                        edgeWeightToParent[nextNode] = weight;
                        q.offer(nextNode);
                    }
                }
            }

            // Backtrack from v to u to get path weights
            Map<Integer, Integer> freq = new HashMap<>();
            int pathLength = 0;
            int curr = v;
            while (curr != u) {
                int w = edgeWeightToParent[curr];
                freq.put(w, freq.getOrDefault(w, 0) + 1);
                pathLength++;
                curr = parent[curr];
            }

            int maxFreq = 0;
            for (int count : freq.values()) {
                maxFreq = Math.max(maxFreq, count);
            }

            result[i] = pathLength - maxFreq;
        }
        return result;
    }
}
```
### Algorithm
- For each query `(a, b)`:
  1. Build an adjacency list representation of the tree if not already built. The list should store pairs of `(neighbor, weight)`.
  2. Perform a Breadth-First Search (BFS) starting from node `a` to find the unique path to node `b`. During the BFS, maintain a `parent` array to reconstruct the path later. `parent[i]` will store the node from which we reached node `i`.
  3. Once the BFS reaches `b`, the search can stop. The path is now implicitly stored in the `parent` array.
  4. Reconstruct the path by backtracking from `b` to `a` using the `parent` array. While backtracking from a node `curr` to its parent `p = parent[curr]`, find the weight of the edge `(curr, p)`.
  5. Store the frequencies of all edge weights encountered on the path in a hash map or an array.
  6. Keep track of the total number of edges on the path (`pathLength`).
  7. After collecting all weights, find the maximum frequency (`maxFreq`) among them.
  8. The minimum number of operations for the query is `pathLength - maxFreq`.

## Lowest Common Ancestor (LCA) with Prefix Counts
A much more efficient approach involves precomputation. The key observation is that the path between any two nodes `a` and `b` goes through their Lowest Common Ancestor (LCA). By precomputing information about paths from the root to every node, we can answer queries about paths between any two nodes quickly. Specifically, we can precompute the counts of each edge weight on the path from the root to every node. This turns the problem of finding frequencies on a path `a-b` into a constant number of lookups using the precomputed values for `a`, `b`, and `lca(a, b)`.
**Time:** O((N+M) * (log N + W_max)), where N is nodes, M is queries, and W_max is max weight. Preprocessing takes O(N * (log N + W_max)) for DFS and building tables. Each query takes O(log N + W_max) for LCA and frequency calculation. · **Space:** O(N * (log N + W_max)), where N is the number of nodes and W_max is the maximum weight value. This space is used for the adjacency list, depth array, binary lifting table `parent` (O(N log N)), and the prefix counts table `counts` (O(N * W_max)).
**Pros:** Extremely efficient for a large number of queries.; The 'query' part of the time complexity is very low, making it suitable for online query processing.
**Cons:** More complex to implement, requiring knowledge of advanced tree algorithms like LCA and binary lifting.; Requires significant preprocessing time and space, which might be overkill for a very small number of queries.
### Explanation
This approach is divided into two phases: preprocessing and query answering.

**Preprocessing:**
First, we traverse the tree using DFS from a root (say, node 0). This traversal allows us to compute several key pieces of information for each node `u`:
- `depth[u]`: The distance from the root to `u`.
- `parent[u][0]`: The immediate parent of `u`.
- `counts[u]`: An array where `counts[u][w]` stores the total count of edges with weight `w` on the path from the root to `u`. This is a form of prefix sum on the tree.

Next, we use the `parent[u][0]` information to build a binary lifting table, `parent[u][j]`, which allows us to find the `2^j`-th ancestor of any node `u` in `O(1)` time. Building this table takes `O(N log N)` time.

**Query Answering:**
For each query `(a, b)`:
1.  We first find their Lowest Common Ancestor, `l = lca(a, b)`, in `O(log N)` time using the binary lifting table.
2.  The total number of edges on the path `a -> b` is `depth[a] + depth[b] - 2 * depth[l]`.
3.  The count of a specific weight `w` on the path `a -> b` is the sum of counts on paths `root -> a` and `root -> b`, minus the counts on the overlapping path `root -> l` counted twice. So, `freq(w) = counts[a][w] + counts[b][w] - 2 * counts[l][w]`.
4.  We compute this for all possible weights (1 to 26) to find the maximum frequency `maxFreq`.
5.  The final answer is `pathLength - maxFreq`.

This method processes each query very quickly after an initial setup cost.

```java
import java.util.*;

class Solution {
    private static final int MAX_WEIGHT = 27;
    private List<int[]>[] adj;
    private int[][] parent;
    private int[][] counts;
    private int[] depth;
    private int LOG_N;

    public int[] minOperationsQueries(int n, int[][] edges, int[][] queries) {
        adj = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            adj[edge[0]].add(new int[]{edge[1], edge[2]});
            adj[edge[1]].add(new int[]{edge[0], edge[2]});
        }

        LOG_N = (int) (Math.log(n) / Math.log(2)) + 1;
        parent = new int[n][LOG_N];
        for (int i = 0; i < n; i++) {
            Arrays.fill(parent[i], -1);
        }
        counts = new int[n][MAX_WEIGHT];
        depth = new int[n];

        dfs(0, -1, 0);

        for (int j = 1; j < LOG_N; j++) {
            for (int i = 0; i < n; i++) {
                if (parent[i][j - 1] != -1) {
                    parent[i][j] = parent[parent[i][j - 1]][j - 1];
                }
            }
        }

        int[] result = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int u = queries[i][0];
            int v = queries[i][1];
            
            if (u == v) {
                result[i] = 0;
                continue;
            }

            int lcaNode = lca(u, v);
            int pathLength = depth[u] + depth[v] - 2 * depth[lcaNode];
            
            int maxFreq = 0;
            for (int w = 1; w < MAX_WEIGHT; w++) {
                int freqOnPath = counts[u][w] + counts[v][w] - 2 * counts[lcaNode][w];
                maxFreq = Math.max(maxFreq, freqOnPath);
            }
            
            result[i] = pathLength - maxFreq;
        }
        return result;
    }

    private void dfs(int u, int p, int d) {
        parent[u][0] = p;
        depth[u] = d;
        for (int[] neighbor : adj[u]) {
            int v = neighbor[0];
            int w = neighbor[1];
            if (v != p) {
                System.arraycopy(counts[u], 0, counts[v], 0, MAX_WEIGHT);
                counts[v][w]++;
                dfs(v, u, d + 1);
            }
        }
    }

    private int lca(int u, int v) {
        if (depth[u] < depth[v]) {
            int temp = u; u = v; v = temp;
        }

        for (int j = LOG_N - 1; j >= 0; j--) {
            if (depth[u] - (1 << j) >= depth[v]) {
                u = parent[u][j];
            }
        }

        if (u == v) return u;

        for (int j = LOG_N - 1; j >= 0; j--) {
            if (parent[u][j] != -1 && parent[u][j] != parent[v][j]) {
                u = parent[u][j];
                v = parent[v][j];
            }
        }
        return parent[u][0];
    }
}
```
### Algorithm
1.  **Preprocessing:**
    a.  Build an adjacency list for the tree.
    b.  Perform a single DFS traversal starting from the root (e.g., node 0). During the traversal, compute:
        i.  `depth[u]`: The depth of each node `u`.
        ii. `parent[u][0]`: The direct parent of `u` (the `2^0`-th ancestor).
        iii. `counts[u][w]`: An array of prefix counts, where `counts[u][w]` is the number of edges with weight `w` on the path from the root to `u`.
    c.  Build a binary lifting table `parent[u][j]` which stores the `2^j`-th ancestor of `u`. This can be done with dynamic programming: `parent[u][j] = parent[parent[u][j-1]][j-1]`.

2.  **Query Processing:**
    a.  For each query `(a, b)`:
    b.  Find the Lowest Common Ancestor, `l = lca(a, b)`, using the precomputed binary lifting table. This takes `O(log N)` time.
    c.  The path from `a` to `b` is composed of the path from `a` to `l` and the path from `b` to `l`. The total number of edges on this path is `pathLength = depth[a] + depth[b] - 2 * depth[l]`.
    d.  The frequency of any weight `w` on the path from `a` to `b` can be calculated using the precomputed prefix counts: `freq(w) = counts[a][w] + counts[b][w] - 2 * counts[l][w]`.
    e.  Iterate through all possible weights (1 to 26) to find the maximum frequency `maxFreq` on the path.
    f.  The result for the query is `pathLength - maxFreq`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> minOperationsQueries(int n, vector<vector<int>> &edges,
                                   vector<vector<int>> &queries) {
    int m = 32 - __builtin_clz(n);
    vector<pair<int, int>> g[n];
    int f[n][m];
    int p[n];
    int cnt[n][26];
    int depth[n];
    memset(f, 0, sizeof(f));
    memset(cnt, 0, sizeof(cnt));
    memset(depth, 0, sizeof(depth));
    memset(p, 0, sizeof(p));
    for (auto &e : edges) {
      int u = e[0], v = e[1], w = e[2] - 1;
      g[u].emplace_back(v, w);
      g[v].emplace_back(u, w);
    }
    queue<int> q;
    q.push(0);
    while (!q.empty()) {
      int i = q.front();
      q.pop();
      f[i][0] = p[i];
      for (int j = 1; j < m; ++j) {
        f[i][j] = f[f[i][j - 1]][j - 1];
      }
      for (auto &[j, w] : g[i]) {
        if (j != p[i]) {
          p[j] = i;
          memcpy(cnt[j], cnt[i], sizeof(cnt[i]));
          cnt[j][w]++;
          depth[j] = depth[i] + 1;
          q.push(j);
        }
      }
    }
    vector<int> ans;
    for (auto &qq : queries) {
      int u = qq[0], v = qq[1];
      int x = u, y = v;
      if (depth[x] < depth[y]) {
        swap(x, y);
      }
      for (int j = m - 1; ~j; --j) {
        if (depth[x] - depth[y] >= (1 << j)) {
          x = f[x][j];
        }
      }
      for (int j = m - 1; ~j; --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 = max(mx, cnt[u][j] + cnt[v][j] - 2 * cnt[x][j]);
      }
      ans.push_back(depth[u] + depth[v] - 2 * depth[x] - mx);
    }
    return ans;
  }
};

```

### Python

```python
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

```