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

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


![](https://assets.leetcode.com/uploads/2023/08/11/graph-6-1.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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


![](https://assets.leetcode.com/uploads/2023/08/11/graph-9-1.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 <= 10^4
  • 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 * 10^4
  • queries[i].length == 2
  • 0 <= ai, bi < n

Solution

Method 1 – Path Frequency Counting with LCA

Intuition

For each query, we need to find the path between two nodes and count the frequency of each edge weight on that path. The minimum number of operations is the number of edges minus the maximum frequency of any weight on the path. To efficiently find the path and its weights, we use Lowest Common Ancestor (LCA) and prefix frequency arrays for each node.

Approach

  1. Build the tree as an adjacency list, storing edge weights.
  2. Preprocess the tree with DFS to record parent, depth, and prefix frequency of edge weights for each node.
  3. For each query, find the LCA of the two nodes.
  4. For each possible weight, calculate its frequency on the path using prefix frequency arrays and the LCA.
  5. The answer for each query is the path length minus the maximum frequency found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

class Solution {
public:
    vector<int> minOperationsQueries(int n, vector<vector<int>>& edges, vector<vector<int>>& queries) {
        vector<vector<pair<int,int>>> g(n);
        for (auto& e : edges) {
            g[e[0]].push_back({e[1], e[2]});
            g[e[1]].push_back({e[0], e[2]});
        }
        int LOG = 15;
        vector<vector<int>> up(n, vector<int>(LOG)), freq(n, vector<int>(27));
        vector<int> depth(n);
        function<void(int,int)> dfs = [&](int u, int p) {
            up[u][0] = p;
            for (int k = 1; k < LOG; ++k)
                up[u][k] = up[up[u][k-1]][k-1];
            for (auto& [v, w] : g[u]) {
                if (v == p) continue;
                depth[v] = depth[u] + 1;
                freq[v] = freq[u];
                freq[v][w]++;
                dfs(v, u);
            }
        };
        dfs(0, 0);
        auto lca = [&](int u, int v) {
            if (depth[u] < depth[v]) swap(u, v);
            for (int k = LOG-1; k >= 0; --k)
                if (depth[up[u][k]] >= depth[v]) u = up[u][k];
            if (u == v) return u;
            for (int k = LOG-1; k >= 0; --k)
                if (up[u][k] != up[v][k]) u = up[u][k], v = up[v][k];
            return up[u][0];
        };
        vector<int> ans;
        for (auto& q : queries) {
            int u = q[0], v = q[1], x = lca(u, v);
            int path_len = depth[u] + depth[v] - 2 * depth[x];
            int mx = 0;
            for (int w = 1; w <= 26; ++w) {
                int cnt = freq[u][w] + freq[v][w] - 2 * freq[x][w];
                mx = max(mx, cnt);
            }
            ans.push_back(path_len - mx);
        }
        return ans;
    }
};
1

// Omitted for brevity, similar logic as C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

class Solution {
    public int[] minOperationsQueries(int n, int[][] edges, int[][] queries) {
        List<int[]>[] g = new ArrayList[n];
        for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
        for (int[] e : edges) {
            g[e[0]].add(new int[]{e[1], e[2]});
            g[e[1]].add(new int[]{e[0], e[2]});
        }
        int LOG = 15;
        int[][] up = new int[n][LOG];
        int[][] freq = new int[n][27];
        int[] depth = new int[n];
        dfs(0, 0, g, up, freq, depth);
        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int u = queries[i][0], v = queries[i][1], x = lca(u, v, up, depth);
            int pathLen = depth[u] + depth[v] - 2 * depth[x];
            int mx = 0;
            for (int w = 1; w <= 26; w++) {
                int cnt = freq[u][w] + freq[v][w] - 2 * freq[x][w];
                mx = Math.max(mx, cnt);
            }
            ans[i] = pathLen - mx;
        }
        return ans;
    }
    private void dfs(int u, int p, List<int[]>[] g, int[][] up, int[][] freq, int[] depth) {
        up[u][0] = p;
        for (int k = 1; k < up[0].length; k++)
            up[u][k] = up[up[u][k-1]][k-1];
        for (int[] e : g[u]) {
            int v = e[0], w = e[1];
            if (v == p) continue;
            depth[v] = depth[u] + 1;
            System.arraycopy(freq[u], 0, freq[v], 0, 27);
            freq[v][w]++;
            dfs(v, u, g, up, freq, depth);
        }
    }
    private int lca(int u, int v, int[][] up, int[] depth) {
        if (depth[u] < depth[v]) { int t = u; u = v; v = t; }
        for (int k = up[0].length-1; k >= 0; k--)
            if (depth[up[u][k]] >= depth[v]) u = up[u][k];
        if (u == v) return u;
        for (int k = up[0].length-1; k >= 0; k--)
            if (up[u][k] != up[v][k]) { u = up[u][k]; v = up[v][k]; }
        return up[u][0];
    }
}
1

// Omitted for brevity, similar logic as Java
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

def min_operations_queries(n: int, edges: list[list[int]], queries: list[list[int]]) -> list[int]:
    from collections import defaultdict
    g = defaultdict(list)
    for u, v, w in edges:
        g[u].append((v, w))
        g[v].append((u, w))
    LOG = 15
    up = [[0]*LOG for _ in range(n)]
    freq = [[0]*27 for _ in range(n)]
    depth = [0]*n
    def dfs(u: int, p: int):
        up[u][0] = p
        for k in range(1, LOG):
            up[u][k] = up[up[u][k-1]][k-1]
        for v, w in g[u]:
            if v == p: continue
            depth[v] = depth[u] + 1
            freq[v] = freq[u][:]
            freq[v][w] += 1
            dfs(v, u)
    dfs(0, 0)
    def lca(u: int, v: int) -> int:
        if depth[u] < depth[v]: u, v = v, u
        for k in range(LOG-1, -1, -1):
            if depth[up[u][k]] >= depth[v]: u = up[u][k]
        if u == v: return u
        for k in range(LOG-1, -1, -1):
            if up[u][k] != up[v][k]: u, v = up[u][k], up[v][k]
        return up[u][0]
    ans = []
    for u, v in queries:
        x = lca(u, v)
        path_len = depth[u] + depth[v] - 2 * depth[x]
        mx = 0
        for w in range(1, 27):
            cnt = freq[u][w] + freq[v][w] - 2 * freq[x][w]
            mx = max(mx, cnt)
        ans.append(path_len - mx)
    return ans
1

// Omitted for brevity, similar logic as C++

1

// Omitted for brevity, similar logic as JavaScript

Complexity

  • ⏰ Time complexity: O((n + m) * log n + m * k), where n is the number of nodes, m is the number of queries, and k is the number of possible weights (<=26). Each query is processed in O(log n + k).
  • 🧺 Space complexity: O(n * k), for prefix frequency arrays and LCA tables.