Facebook Pixel

2846. Minimum Edge Weight Equilibrium Queries in a Tree

HardTreeGraphArrayStrongly Connected Component
Leetcode Link

Problem Description

You are given an undirected tree with n nodes labeled from 0 to n - 1. The tree is represented by:

  • An integer n (number of nodes)
  • A 2D integer array edges of length n - 1, where edges[i] = [ui, vi, wi] indicates an edge between nodes ui and vi with weight wi

You are also given a 2D integer array queries of length m, where queries[i] = [ai, bi] represents a query asking about the path from node ai to node bi.

For each query, you need to find the minimum number of operations required to make all edge weights on the path from ai to bi equal. In one operation, you can:

  • Choose any edge in the tree
  • Change its weight to any value

Important notes:

  • Each query is independent - the tree returns to its initial state before processing each new query
  • The path from ai to bi is a sequence of distinct nodes starting at ai and ending at bi, where every two adjacent nodes in the sequence share an edge

The task is to return an array answer of length m where answer[i] is the minimum number of operations needed for the i-th query.

Example understanding: If a path from node a to node b has edges with weights [1, 2, 1, 3, 1], to make all weights equal, we could change them all to 1 (the most frequent weight). This would require changing the weights 2 and 3, resulting in 2 operations.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

To make all edge weights equal on a path, we need to change some edges to have the same weight. The key insight is that we should change all edges to the weight that appears most frequently on the path - this minimizes the number of changes needed.

For example, if a path has edges with weights [1, 2, 1, 3, 1], we have:

  • Weight 1 appears 3 times
  • Weight 2 appears 1 time
  • Weight 3 appears 1 time

The optimal strategy is to change everything to weight 1, requiring only 2 operations (changing the 2 and the 3).

This leads us to the formula: minimum operations = total edges on path - frequency of most common weight

Now, how do we efficiently find this information for any path between two nodes?

  1. Finding the path length: In a tree, there's exactly one path between any two nodes. The path from node u to node v goes through their Lowest Common Ancestor (LCA). If we know the depths of u, v, and their LCA x, the path length is depth[u] + depth[v] - 2 * depth[x].

  2. Counting edge weights on the path: We can precompute for each node how many times each weight appears on the path from the root to that node. Let's call this cnt[node][weight]. Then, for a path from u to v through LCA x, the frequency of weight w on this path is cnt[u][w] + cnt[v][w] - 2 * cnt[x][w] (we subtract the LCA's count twice because the path to LCA is counted in both u and v).

  3. Finding LCA efficiently: Since we may have many queries, we need a fast way to find the LCA. Binary lifting is perfect for this - it preprocesses the tree to answer LCA queries in O(log n) time by storing the 2^j-th ancestor of each node.

The solution combines these ideas: preprocess the tree with binary lifting and weight counts, then for each query, find the LCA, calculate the path length, find the maximum weight frequency on that path, and subtract it from the path length.

Learn more about Tree and Graph patterns.

Solution Approach

The solution uses Binary Lifting to efficiently find the Lowest Common Ancestor (LCA) and track edge weight frequencies along paths. Let's walk through the implementation step by step:

1. Data Structure Initialization

m = n.bit_length()  # Maximum power of 2 needed for binary lifting
g = [[] for _ in range(n)]  # Adjacency list for the [tree](/problems/tree_intro)
f = [[0] * m for _ in range(n)]  # Binary lifting table: f[i][j] = 2^j-th ancestor of node i
p = [0] * n  # Direct parent of each node
cnt = [None] * n  # cnt[i][w] = count of weight w from root to node i
depth = [0] * n  # Depth of each node from root

2. Building the Tree Structure

First, we convert the edge list into an adjacency list representation. Since edge weights range from 1 to 26, we store them as 0-25 internally:

for u, v, w in edges:
    g[u].append((v, w - 1))  # Store weight as 0-indexed
    g[v].append((u, w - 1))

3. Preprocessing with BFS

We perform a BFS from the root (node 0) to:

  • Build the binary lifting table f
  • Track the depth of each node
  • Count edge weight frequencies from root to each node
cnt[0] = [0] * 26  # Root has no edges above it
q = deque([0])
while q:
    i = q.popleft()
    f[i][0] = p[i]  # Direct parent
  
    # Fill binary lifting table: 2^j-th ancestor = 2^(j-1)-th ancestor of 2^(j-1)-th ancestor
    for j in range(1, m):
        f[i][j] = f[f[i][j - 1]][j - 1]
  
    # Process children
    for j, w in g[i]:
        if j != p[i]:  # Avoid going back to parent
            p[j] = i
            cnt[j] = cnt[i][:]  # Copy parent's weight counts
            cnt[j][w] += 1  # Add current edge weight
            depth[j] = depth[i] + 1
            q.append(j)

4. Processing Queries

For each query (u, v), we need to find their LCA and calculate the minimum operations:

Finding LCA using Binary Lifting:

x, y = u, v
# Step 1: Make x the deeper node
if depth[x] < depth[y]:
    x, y = y, x

# Step 2: Lift x to the same depth as y
for j in reversed(range(m)):
    if depth[x] - depth[y] >= (1 << j):
        x = f[x][j]

# Step 3: Lift both nodes simultaneously until they meet at LCA
for j in reversed(range(m)):
    if f[x][j] != f[y][j]:
        x, y = f[x][j], f[y][j]

# If x != y, their parent is the LCA
if x != y:
    x = p[x]  # x is now the LCA

Calculating Minimum Operations:

Once we have the LCA x, we can calculate:

  1. Path length: depth[u] + depth[v] - 2 * depth[x]

  2. Maximum weight frequency on path: For each weight j from 0 to 25, the frequency on the path from u to v is cnt[u][j] + cnt[v][j] - 2 * cnt[x][j]. We find the maximum among all weights.

  3. Minimum operations: Path length minus maximum frequency

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)

Time Complexity

  • Preprocessing: O(n log n) for building the binary lifting table
  • Per query: O(log n) for finding LCA + O(26) for finding maximum frequency = O(log n)
  • Total: O(n log n + q log n) where q is the number of queries

Space Complexity

  • O(n log n) for the binary lifting table
  • O(26n) for the weight frequency counts
  • Overall: O(n log n)

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Given:

  • Tree with 5 nodes (0-4)
  • Edges: [[0,1,2], [1,2,3], [1,3,2], [3,4,3]]
  • Query: Find minimum operations for path from node 2 to node 4

Step 1: Build the Tree

    0
    |
   (2)
    |
    1
   / \
 (3)  (2)
 /     \
2       3
        |
       (3)
        |
        4

Numbers in parentheses are edge weights.

Step 2: Preprocessing with BFS from root (node 0)

After BFS, we have:

  • depth: [0, 1, 2, 2, 3]
  • parent: [0, 0, 1, 1, 3]
  • cnt (weight frequencies from root):
    • Node 0: weight 2 appears 0 times, weight 3 appears 0 times
    • Node 1: weight 2 appears 1 time (edge 0→1)
    • Node 2: weight 2 appears 1 time, weight 3 appears 1 time (edges 0→1→2)
    • Node 3: weight 2 appears 2 times (edges 0→1→3)
    • Node 4: weight 2 appears 2 times, weight 3 appears 1 time (edges 0→1→3→4)

Step 3: Process Query (2, 4)

Finding LCA of nodes 2 and 4:

  • Node 2 is at depth 2, node 4 is at depth 3
  • Make node 4 jump to same depth as node 2: node 4 → node 3 (now both at depth 2)
  • Both nodes jump up simultaneously: node 2 → node 1, node 3 → node 1
  • They meet at node 1, so LCA = 1

Step 4: Calculate Path Information

Path from 2 to 4 goes: 2 → 1 → 3 → 4

Path length = depth[2] + depth[4] - 2×depth[1] = 2 + 3 - 2×1 = 3 edges

Weight frequencies on path:

  • For weight 2: cnt[2][2] + cnt[4][2] - 2×cnt[1][2] = 1 + 2 - 2×1 = 1
  • For weight 3: cnt[2][3] + cnt[4][3] - 2×cnt[1][3] = 1 + 1 - 2×0 = 2

The path has edges with weights [3, 2, 3], confirming:

  • Weight 2 appears 1 time
  • Weight 3 appears 2 times

Maximum frequency = 2 (weight 3 appears most)

Step 5: Calculate Answer

Minimum operations = Path length - Maximum frequency = 3 - 2 = 1

We need to change only 1 edge (the edge with weight 2) to make all weights equal to 3.

Another Query Example: (0, 2)

Path: 0 → 1 → 2 (edges with weights [2, 3])

  • LCA of 0 and 2 is node 0 (since 0 is ancestor of 2)
  • Path length = depth[0] + depth[2] - 2×depth[0] = 0 + 2 - 0 = 2
  • Weight 2 frequency: cnt[0][2] + cnt[2][2] - 2×cnt[0][2] = 0 + 1 - 0 = 1
  • Weight 3 frequency: cnt[0][3] + cnt[2][3] - 2×cnt[0][3] = 0 + 1 - 0 = 1
  • Maximum frequency = 1
  • Minimum operations = 2 - 1 = 1

This makes sense: we have weights [2, 3] on the path, and we need to change 1 of them to make both equal.

Solution Implementation

1class Solution:
2    def minOperationsQueries(
3        self, n: int, edges: List[List[int]], queries: List[List[int]]
4    ) -> List[int]:
5        # Calculate maximum number of bits needed for binary lifting
6        max_log = n.bit_length()
7      
8        # Build adjacency list for the tree
9        graph = [[] for _ in range(n)]
10        for u, v, weight in edges:
11            # Convert weight to 0-indexed (weights are 1-26, store as 0-25)
12            graph[u].append((v, weight - 1))
13            graph[v].append((u, weight - 1))
14      
15        # Binary lifting table: ancestor[node][power] = 2^power-th ancestor of node
16        ancestor = [[0] * max_log for _ in range(n)]
17      
18        # Parent of each node
19        parent = [0] * n
20      
21        # Weight frequency count from root to each node
22        weight_count = [None] * n
23      
24        # Depth of each node from root
25        depth = [0] * n
26      
27        # Initialize root node (node 0)
28        weight_count[0] = [0] * 26  # 26 possible weights
29      
30        # BFS to build the tree structure
31        queue = deque([0])
32        while queue:
33            current_node = queue.popleft()
34          
35            # Build binary lifting table for current node
36            ancestor[current_node][0] = parent[current_node]
37            for power in range(1, max_log):
38                ancestor[current_node][power] = ancestor[ancestor[current_node][power - 1]][power - 1]
39          
40            # Process neighbors
41            for neighbor, edge_weight in graph[current_node]:
42                if neighbor != parent[current_node]:
43                    # Set parent relationship
44                    parent[neighbor] = current_node
45                  
46                    # Copy weight counts and increment current edge weight
47                    weight_count[neighbor] = weight_count[current_node][:]
48                    weight_count[neighbor][edge_weight] += 1
49                  
50                    # Update depth
51                    depth[neighbor] = depth[current_node] + 1
52                  
53                    # Add to queue for processing
54                    queue.append(neighbor)
55      
56        # Process each query
57        result = []
58        for u, v in queries:
59            # Find LCA using binary lifting
60            node_x, node_y = u, v
61          
62            # Ensure node_x is deeper or at same level as node_y
63            if depth[node_x] < depth[node_y]:
64                node_x, node_y = node_y, node_x
65          
66            # Lift node_x to the same level as node_y
67            for power in reversed(range(max_log)):
68                if depth[node_x] - depth[node_y] >= (1 << power):
69                    node_x = ancestor[node_x][power]
70          
71            # Lift both nodes until they meet at LCA
72            for power in reversed(range(max_log)):
73                if ancestor[node_x][power] != ancestor[node_y][power]:
74                    node_x = ancestor[node_x][power]
75                    node_y = ancestor[node_y][power]
76          
77            # If nodes are different, their parent is the LCA
78            if node_x != node_y:
79                node_x = parent[node_x]
80          
81            lca = node_x
82          
83            # Calculate the most frequent weight on the path from u to v
84            max_weight_frequency = max(
85                weight_count[u][weight_type] + weight_count[v][weight_type] - 2 * weight_count[lca][weight_type]
86                for weight_type in range(26)
87            )
88          
89            # Total path length minus most frequent weight gives minimum operations
90            path_length = depth[u] + depth[v] - 2 * depth[lca]
91            min_operations = path_length - max_weight_frequency
92          
93            result.append(min_operations)
94      
95        return result
96
1class Solution {
2    public int[] minOperationsQueries(int n, int[][] edges, int[][] queries) {
3        // Calculate the maximum power of 2 needed for binary lifting
4        int maxPower = 32 - Integer.numberOfLeadingZeros(n);
5      
6        // Build adjacency list for the tree
7        List<int[]>[] graph = new List[n];
8        Arrays.setAll(graph, i -> new ArrayList<>());
9      
10        // Binary lifting table: ancestor[node][power] = 2^power-th ancestor of node
11        int[][] ancestor = new int[n][maxPower];
12      
13        // Parent array for each node
14        int[] parent = new int[n];
15      
16        // Count of each weight (1-26) from root to each node
17        int[][] weightCount = new int[n][0];
18      
19        // Depth of each node from root
20        int[] depth = new int[n];
21      
22        // Build the graph from edges (convert weights from 1-based to 0-based)
23        for (int[] edge : edges) {
24            int u = edge[0];
25            int v = edge[1];
26            int weight = edge[2] - 1;  // Convert to 0-based indexing
27            graph[u].add(new int[] {v, weight});
28            graph[v].add(new int[] {u, weight});
29        }
30      
31        // Initialize root node's weight count array
32        weightCount[0] = new int[26];
33      
34        // BFS to build the tree structure and compute necessary arrays
35        Deque<Integer> queue = new ArrayDeque<>();
36        queue.offer(0);
37      
38        while (!queue.isEmpty()) {
39            int currentNode = queue.poll();
40          
41            // Set immediate parent for binary lifting
42            ancestor[currentNode][0] = parent[currentNode];
43          
44            // Fill binary lifting table using dynamic programming
45            for (int power = 1; power < maxPower; power++) {
46                ancestor[currentNode][power] = ancestor[ancestor[currentNode][power - 1]][power - 1];
47            }
48          
49            // Process all neighbors
50            for (int[] neighbor : graph[currentNode]) {
51                int nextNode = neighbor[0];
52                int edgeWeight = neighbor[1];
53              
54                // Skip if this is the parent (avoid going back)
55                if (nextNode != parent[currentNode]) {
56                    parent[nextNode] = currentNode;
57                  
58                    // Copy weight counts from parent and increment current edge weight
59                    weightCount[nextNode] = weightCount[currentNode].clone();
60                    weightCount[nextNode][edgeWeight]++;
61                  
62                    // Update depth
63                    depth[nextNode] = depth[currentNode] + 1;
64                  
65                    queue.offer(nextNode);
66                }
67            }
68        }
69      
70        // Process queries
71        int numQueries = queries.length;
72        int[] result = new int[numQueries];
73      
74        for (int i = 0; i < numQueries; i++) {
75            int nodeU = queries[i][0];
76            int nodeV = queries[i][1];
77          
78            // Find LCA using binary lifting
79            int x = nodeU;
80            int y = nodeV;
81          
82            // Ensure x is at deeper or same depth as y
83            if (depth[x] < depth[y]) {
84                int temp = x;
85                x = y;
86                y = temp;
87            }
88          
89            // Lift x to the same level as y
90            for (int power = maxPower - 1; power >= 0; power--) {
91                if (depth[x] - depth[y] >= (1 << power)) {
92                    x = ancestor[x][power];
93                }
94            }
95          
96            // Lift both nodes until they meet at LCA
97            for (int power = maxPower - 1; power >= 0; power--) {
98                if (ancestor[x][power] != ancestor[y][power]) {
99                    x = ancestor[x][power];
100                    y = ancestor[y][power];
101                }
102            }
103          
104            // If nodes are different, their parent is the LCA
105            if (x != y) {
106                x = parent[x];
107            }
108          
109            // x is now the LCA
110            int lca = x;
111          
112            // Find the maximum count of any single weight on the path
113            int maxSingleWeight = 0;
114            for (int weight = 0; weight < 26; weight++) {
115                int pathWeightCount = weightCount[nodeU][weight] + weightCount[nodeV][weight] 
116                                     - 2 * weightCount[lca][weight];
117                maxSingleWeight = Math.max(maxSingleWeight, pathWeightCount);
118            }
119          
120            // Calculate minimum operations needed
121            // Total edges on path - edges with most frequent weight
122            int totalEdges = depth[nodeU] + depth[nodeV] - 2 * depth[lca];
123            result[i] = totalEdges - maxSingleWeight;
124        }
125      
126        return result;
127    }
128}
129
1class Solution {
2public:
3    vector<int> minOperationsQueries(int n, vector<vector<int>>& edges, vector<vector<int>>& queries) {
4        // Calculate the maximum depth for binary lifting (log2(n))
5        int maxDepth = 32 - __builtin_clz(n);
6      
7        // Build adjacency list: g[node] = {neighbor, weight}
8        vector<vector<pair<int, int>>> graph(n);
9      
10        // Binary lifting table: ancestor[node][j] = 2^j-th ancestor of node
11        vector<vector<int>> ancestor(n, vector<int>(maxDepth, 0));
12      
13        // Parent of each node
14        vector<int> parent(n, 0);
15      
16        // Count of each weight (1-26) from root to each node
17        vector<vector<int>> weightCount(n, vector<int>(26, 0));
18      
19        // Depth of each node from root
20        vector<int> depth(n, 0);
21      
22        // Build the graph from edges
23        for (auto& edge : edges) {
24            int u = edge[0];
25            int v = edge[1];
26            int weight = edge[2] - 1;  // Convert weight from 1-based to 0-based
27            graph[u].emplace_back(v, weight);
28            graph[v].emplace_back(u, weight);
29        }
30      
31        // BFS to build the tree and precompute necessary information
32        queue<int> bfsQueue;
33        bfsQueue.push(0);  // Start from node 0 as root
34      
35        while (!bfsQueue.empty()) {
36            int currentNode = bfsQueue.front();
37            bfsQueue.pop();
38          
39            // Set up binary lifting table for current node
40            ancestor[currentNode][0] = parent[currentNode];
41            for (int j = 1; j < maxDepth; ++j) {
42                ancestor[currentNode][j] = ancestor[ancestor[currentNode][j - 1]][j - 1];
43            }
44          
45            // Process all neighbors of current node
46            for (auto& [neighbor, weight] : graph[currentNode]) {
47                if (neighbor != parent[currentNode]) {
48                    // Set parent relationship
49                    parent[neighbor] = currentNode;
50                  
51                    // Copy weight counts from parent and increment current weight
52                    for (int k = 0; k < 26; ++k) {
53                        weightCount[neighbor][k] = weightCount[currentNode][k];
54                    }
55                    weightCount[neighbor][weight]++;
56                  
57                    // Update depth
58                    depth[neighbor] = depth[currentNode] + 1;
59                  
60                    // Add to BFS queue
61                    bfsQueue.push(neighbor);
62                }
63            }
64        }
65      
66        vector<int> result;
67      
68        // Process each query
69        for (auto& query : queries) {
70            int u = query[0];
71            int v = query[1];
72          
73            // Find LCA (Lowest Common Ancestor) using binary lifting
74            int nodeA = u;
75            int nodeB = v;
76          
77            // Make sure nodeA is deeper than or equal to nodeB
78            if (depth[nodeA] < depth[nodeB]) {
79                swap(nodeA, nodeB);
80            }
81          
82            // Lift nodeA to the same level as nodeB
83            for (int j = maxDepth - 1; j >= 0; --j) {
84                if (depth[nodeA] - depth[nodeB] >= (1 << j)) {
85                    nodeA = ancestor[nodeA][j];
86                }
87            }
88          
89            // Find LCA by lifting both nodes simultaneously
90            for (int j = maxDepth - 1; j >= 0; --j) {
91                if (ancestor[nodeA][j] != ancestor[nodeB][j]) {
92                    nodeA = ancestor[nodeA][j];
93                    nodeB = ancestor[nodeB][j];
94                }
95            }
96          
97            // If nodes are different, their parent is the LCA
98            if (nodeA != nodeB) {
99                nodeA = parent[nodeA];
100            }
101          
102            int lca = nodeA;
103          
104            // Find the maximum frequency of any weight on the path
105            int maxWeightFreq = 0;
106            for (int weight = 0; weight < 26; ++weight) {
107                // Count of weight on path from u to v through LCA
108                int pathWeightCount = weightCount[u][weight] + weightCount[v][weight] - 2 * weightCount[lca][weight];
109                maxWeightFreq = max(maxWeightFreq, pathWeightCount);
110            }
111          
112            // Total edges on path - edges with most frequent weight = minimum operations
113            int totalEdges = depth[u] + depth[v] - 2 * depth[lca];
114            result.push_back(totalEdges - maxWeightFreq);
115        }
116      
117        return result;
118    }
119};
120
1function minOperationsQueries(n: number, edges: number[][], queries: number[][]): number[] {
2    // Calculate the maximum depth for binary lifting (log2(n))
3    const maxDepth = Math.floor(Math.log2(n)) + 1;
4  
5    // Build adjacency list: graph[node] = array of {neighbor, weight}
6    const graph: Array<Array<{neighbor: number, weight: number}>> = Array(n).fill(null).map(() => []);
7  
8    // Binary lifting table: ancestor[node][j] = 2^j-th ancestor of node
9    const ancestor: number[][] = Array(n).fill(null).map(() => Array(maxDepth).fill(0));
10  
11    // Parent of each node in the tree
12    const parent: number[] = Array(n).fill(0);
13  
14    // Count of each weight (1-26) from root to each node
15    // weightCount[node][weight] = frequency of weight from root to node
16    const weightCount: number[][] = Array(n).fill(null).map(() => Array(26).fill(0));
17  
18    // Depth of each node from root
19    const depth: number[] = Array(n).fill(0);
20  
21    // Build the graph from edges
22    for (const edge of edges) {
23        const u = edge[0];
24        const v = edge[1];
25        const weight = edge[2] - 1; // Convert weight from 1-based to 0-based indexing
26        graph[u].push({neighbor: v, weight: weight});
27        graph[v].push({neighbor: u, weight: weight});
28    }
29  
30    // BFS to build the tree and precompute necessary information
31    const bfsQueue: number[] = [];
32    bfsQueue.push(0); // Start from node 0 as root
33  
34    while (bfsQueue.length > 0) {
35        const currentNode = bfsQueue.shift()!;
36      
37        // Set up binary lifting table for current node
38        // ancestor[node][0] is the immediate parent
39        ancestor[currentNode][0] = parent[currentNode];
40        for (let j = 1; j < maxDepth; j++) {
41            // ancestor[node][j] = 2^j-th ancestor = 2^(j-1)-th ancestor of 2^(j-1)-th ancestor
42            ancestor[currentNode][j] = ancestor[ancestor[currentNode][j - 1]][j - 1];
43        }
44      
45        // Process all neighbors of current node
46        for (const {neighbor, weight} of graph[currentNode]) {
47            // Skip if neighbor is the parent (avoid going back in tree)
48            if (neighbor !== parent[currentNode]) {
49                // Set parent relationship
50                parent[neighbor] = currentNode;
51              
52                // Copy weight counts from parent and increment current edge weight
53                for (let k = 0; k < 26; k++) {
54                    weightCount[neighbor][k] = weightCount[currentNode][k];
55                }
56                weightCount[neighbor][weight]++;
57              
58                // Update depth (one level deeper than parent)
59                depth[neighbor] = depth[currentNode] + 1;
60              
61                // Add to BFS queue for processing
62                bfsQueue.push(neighbor);
63            }
64        }
65    }
66  
67    const result: number[] = [];
68  
69    // Process each query
70    for (const query of queries) {
71        const u = query[0];
72        const v = query[1];
73      
74        // Find LCA (Lowest Common Ancestor) using binary lifting
75        let nodeA = u;
76        let nodeB = v;
77      
78        // Make sure nodeA is deeper than or equal to nodeB
79        if (depth[nodeA] < depth[nodeB]) {
80            [nodeA, nodeB] = [nodeB, nodeA];
81        }
82      
83        // Lift nodeA to the same level as nodeB
84        for (let j = maxDepth - 1; j >= 0; j--) {
85            // Check if we can make a jump of 2^j levels
86            if (depth[nodeA] - depth[nodeB] >= (1 << j)) {
87                nodeA = ancestor[nodeA][j];
88            }
89        }
90      
91        // Find LCA by lifting both nodes simultaneously
92        for (let j = maxDepth - 1; j >= 0; j--) {
93            // If ancestors at 2^j levels are different, we can safely jump
94            if (ancestor[nodeA][j] !== ancestor[nodeB][j]) {
95                nodeA = ancestor[nodeA][j];
96                nodeB = ancestor[nodeB][j];
97            }
98        }
99      
100        // If nodes are different after lifting, their parent is the LCA
101        if (nodeA !== nodeB) {
102            nodeA = parent[nodeA];
103        }
104      
105        const lca = nodeA;
106      
107        // Find the maximum frequency of any weight on the path
108        let maxWeightFreq = 0;
109        for (let weight = 0; weight < 26; weight++) {
110            // Count of weight on path from u to v through LCA
111            // = count(root to u) + count(root to v) - 2 * count(root to lca)
112            const pathWeightCount = weightCount[u][weight] + weightCount[v][weight] - 2 * weightCount[lca][weight];
113            maxWeightFreq = Math.max(maxWeightFreq, pathWeightCount);
114        }
115      
116        // Calculate minimum operations needed
117        // Total edges on path - edges with most frequent weight = minimum operations
118        const totalEdges = depth[u] + depth[v] - 2 * depth[lca];
119        result.push(totalEdges - maxWeightFreq);
120    }
121  
122    return result;
123}
124

Time and Space Complexity

Time Complexity: O((n + q) × C × log n) where:

  • n is the number of nodes
  • q is the number of queries
  • C = 26 (the maximum value of edge weight, as weights range from 1-26)
  • log n comes from the binary lifting preprocessing and LCA computation

The time complexity breaks down as follows:

  1. Preprocessing phase: O(n × log n)
    • Building the adjacency list: O(n)
    • BFS traversal to compute depth, parent relationships, and weight counts: O(n × C)
    • Binary lifting table construction: O(n × log n)
  2. Query phase: O(q × (log n + C))
    • For each query, finding LCA using binary lifting: O(log n)
    • Computing the maximum frequency among all weights: O(C)

Overall: O(n × C + n × log n + q × (log n + C)) = O((n + q) × C × log n)

Space Complexity: O(n × C × log n) where:

  • Binary lifting table f: O(n × log n)
  • Weight count array cnt: O(n × C) where each node stores a frequency array of size 26
  • Adjacency list g: O(n)
  • Other auxiliary arrays (depth, parent): O(n)

The dominant space factor is O(n × C) for the count arrays, but when combined with the binary lifting table, the overall space complexity is O(n × C × log n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect LCA Calculation When One Node is Ancestor of Another

The Pitfall: A critical bug occurs in the LCA finding logic when one node is already the ancestor of another. After lifting the deeper node to the same level as the shallower one, if they become the same node (meaning one was the ancestor of the other), the code still proceeds to the binary lifting loop and incorrectly sets the LCA to the parent of this node.

Example: Consider a path from node 2 to node 0 where node 0 is the root and ancestor of node 2:

  • After lifting node 2 to the same depth as node 0, we get node_x = node_y = 0
  • The code then checks if node_x != node_y: which is false, so it doesn't execute node_x = parent[node_x]
  • However, this means lca = node_x = 0, which is correct by luck
  • But if the query was reversed (0 to 2), after depth adjustment, both would be at node 0, and the LCA would correctly be 0

The issue becomes apparent in other tree structures where the ancestor relationship isn't at the root.

The Solution: Add an early termination check after equalizing depths:

# Lift node_x to the same level as node_y
for power in reversed(range(max_log)):
    if depth[node_x] - depth[node_y] >= (1 << power):
        node_x = ancestor[node_x][power]

# Early termination: if they're already the same, that's the LCA
if node_x == node_y:
    lca = node_x
else:
    # Lift both nodes until they meet at LCA
    for power in reversed(range(max_log)):
        if ancestor[node_x][power] != ancestor[node_y][power]:
            node_x = ancestor[node_x][power]
            node_y = ancestor[node_y][power]
  
    # Their parent is the LCA
    lca = parent[node_x]

2. Off-by-One Error in Weight Indexing

The Pitfall: The problem states weights range from 1 to 26, but the code stores them as 0-25 for array indexing. Forgetting this conversion in any part of the code leads to:

  • Array index out of bounds errors
  • Incorrect weight frequency calculations
  • Wrong answer for minimum operations

Common mistake locations:

  • When building the graph: forgetting weight - 1
  • When processing weight counts: using wrong array size (25 instead of 26)
  • Mixing 0-indexed and 1-indexed weight values in different parts of code

The Solution: Be consistent with the indexing throughout:

# Always convert when reading edges
graph[u].append((v, weight - 1))  # weight - 1 for 0-indexing

# Use correct array size
weight_count[0] = [0] * 26  # 26 possible weights (1-26, stored as 0-25)

# Document the indexing scheme clearly
# Weight w (1-26) is stored at index w-1 (0-25)

3. Parent Tracking During BFS

The Pitfall: When building the tree using BFS, not properly checking if a neighbor is the parent can cause:

  • Creating cycles in parent relationships
  • Incorrect depth calculations
  • Wrong weight frequency counts

The Solution: Always exclude the parent when traversing neighbors:

for neighbor, edge_weight in graph[current_node]:
    if neighbor != parent[current_node]:  # Critical check
        parent[neighbor] = current_node
        # ... rest of the processing
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Which data structure is used in a depth first search?

Recommended Readings

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

Graph Fundamentals

https assets algo monster cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could be disconnected A tree

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More