LeetCode 2846 - Minimum Edge Weight Equilibrium Queries in a Tree

LeetCode Problem 2846

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Bit Manipulation, Tree, Depth-First Search

Solution

Problem Understanding

You are given an undirected weighted tree with n nodes. Since the graph is a tree, there is exactly one simple path between any two nodes.

Each edge has a weight between 1 and 26. For every query [a, b], we look at the unique path from node a to node b. The goal is to determine the minimum number of edge weight changes needed so that every edge on that path has the same weight.

An operation allows changing the weight of any edge to any value. Since queries are independent, modifications made for one query do not affect later queries.

The key observation is that if a path contains edge weights like:

1, 1, 2, 1, 3

then the best strategy is to keep the most frequent weight unchanged and modify all others. In this example, weight 1 appears three times, so we only need to change the 2 and 3.

The minimum operations for a path therefore becomes:

(number of edges on the path) - (maximum frequency of any weight)

The input constraints are important:

• n <= 10^4
• queries.length <= 2 * 10^4
• edge weights are limited to 1..26

The small weight range is extremely important because it allows us to maintain frequency counts efficiently.

A naive solution that recomputes path frequencies for every query independently would become too slow because there can be up to 20,000 queries.

Important edge cases include:

• Queries where a == b, meaning the path contains no edges
• Very deep trees, which could make repeated DFS traversals expensive
• Paths where every edge already has the same weight
• Paths where every edge has a different weight
• Skewed trees that behave like linked lists

The problem guarantees:

• The graph is always a valid tree
• Edge weights are always between 1 and 26
• There is always exactly one path between any pair of nodes

Approaches

Brute Force Approach

The brute force solution processes every query independently.

For each query [a, b]:

1. Run DFS or BFS to find the path between a and b
2. Collect all edge weights along that path
3. Count the frequency of each weight
4. Compute:

path_length - max_frequency

This works because the optimal strategy is always to keep the most common weight unchanged and convert every other edge to that weight.

However, this approach is inefficient. In the worst case, each query may traverse almost the entire tree.

If there are m queries, the total complexity becomes:

O(m * n)

With n = 10^4 and m = 2 * 10^4, this becomes too large.

Optimal Approach

The optimal solution combines two ideas:

1. Lowest Common Ancestor, LCA
2. Prefix frequency counts for edge weights

Instead of recomputing frequencies for every query, we preprocess information during a DFS traversal.

For every node:

• Store its depth
• Store its ancestors for binary lifting
• Store cumulative counts of each edge weight from the root to that node

Then for any query [u, v]:

• Find lca(u, v)
• Compute the frequency of every edge weight on the path using prefix subtraction

If:

count[node][w]

means the number of edges with weight w from root to node, then:

path_count[w] =
count[u][w] + count[v][w] - 2 * count[lca][w]

This works because the root-to-LCA portion is counted twice.

The path length is:

depth[u] + depth[v] - 2 * depth[lca]

Then:

answer = path_length - max(path_count)

Since weights are only from 1 to 26, each query only checks 26 frequencies.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m * n)	O(n)	DFS/BFS for every query
Optimal	O((n log n) + (m log n))	O(n log n + 26n)	Uses LCA and prefix frequency counts

Algorithm Walkthrough

Step 1: Build the Adjacency List

Convert the edge list into an adjacency list.

Each entry stores:

• Neighbor node
• Edge weight

This allows efficient DFS traversal of the tree.

Step 2: Prepare Binary Lifting Tables

We need fast LCA queries.

Create:

parent[k][node]

which stores the 2^kth ancestor of each node.

Also store:

depth[node]

which represents the depth from the root.

Step 3: DFS Traversal From the Root

Choose node 0 as the root.

During DFS:

1. Set depths
2. Fill immediate parent relationships
3. Build cumulative weight frequencies

Define:

freq[node][w]

as the number of edges with weight w on the path from the root to node.

When moving from parent to child through edge weight w:

freq[child] = freq[parent]
freq[child][w] += 1

Because weights are limited to 26, copying these arrays is cheap.

Step 4: Build the Binary Lifting Table

After DFS, compute higher ancestors:

parent[k][node] = parent[k-1][ parent[k-1][node] ]

This enables jumping upward in powers of two.

Step 5: Process Each Query

For query [u, v]:

1. Find lca(u, v)
2. Compute path length:

depth[u] + depth[v] - 2 * depth[lca]

1. Compute weight frequencies on the path:

freq[u][w] + freq[v][w] - 2 * freq[lca][w]

1. Find the maximum frequency
2. Return:

path_length - max_frequency

Step 6: Repeat For All Queries

Store answers in an array and return it.

Why it works

The DFS preprocessing converts every root-to-node path into cumulative frequency data. Since every tree path can be represented as:

u -> lca -> v

we can reconstruct path frequencies using prefix subtraction, exactly like prefix sums in arrays.

The minimum operations are achieved by preserving the most common weight and changing every other edge. Therefore:

minimum_operations =
total_edges - most_frequent_weight_count

This guarantees optimality.

Python Solution

from typing import List
import math

class Solution:
    def minOperationsQueries(
        self,
        n: int,
        edges: List[List[int]],
        queries: List[List[int]]
    ) -> List[int]:

        graph = [[] for _ in range(n)]

        for u, v, w in edges:
            graph[u].append((v, w))
            graph[v].append((u, w))

        log = math.ceil(math.log2(n)) + 1

        parent = [[-1] * n for _ in range(log)]
        depth = [0] * n

        # freq[node][weight]
        freq = [[0] * 27 for _ in range(n)]

        def dfs(node: int, par: int) -> None:
            parent[0][node] = par

            for nei, weight in graph[node]:
                if nei == par:
                    continue

                depth[nei] = depth[node] + 1

                freq[nei] = freq[node][:]

                freq[nei][weight] += 1

                dfs(nei, node)

        dfs(0, -1)

        for k in range(1, log):
            for node in range(n):
                prev = parent[k - 1][node]

                if prev != -1:
                    parent[k][node] = parent[k - 1][prev]

        def lca(u: int, v: int) -> int:
            if depth[u] < depth[v]:
                u, v = v, u

            diff = depth[u] - depth[v]

            for k in range(log):
                if diff & (1 << k):
                    u = parent[k][u]

            if u == v:
                return u

            for k in range(log - 1, -1, -1):
                if parent[k][u] != parent[k][v]:
                    u = parent[k][u]
                    v = parent[k][v]

            return parent[0][u]

        answer = []

        for u, v in queries:
            ancestor = lca(u, v)

            path_length = (
                depth[u] + depth[v] - 2 * depth[ancestor]
            )

            max_frequency = 0

            for weight in range(1, 27):
                count = (
                    freq[u][weight]
                    + freq[v][weight]
                    - 2 * freq[ancestor][weight]
                )

                max_frequency = max(max_frequency, count)

            answer.append(path_length - max_frequency)

        return answer

The implementation begins by building an adjacency list representation of the tree. Each node stores neighboring nodes together with edge weights.

The DFS traversal initializes three important structures:

• depth
• immediate parent references
• cumulative edge weight frequencies

The freq array behaves like a prefix sum over the tree. Each node inherits the frequency counts from its parent, then increments the count for the edge used to reach it.

The binary lifting table is then constructed. Each level stores ancestors at exponentially increasing distances.

The lca function first equalizes depths, then lifts both nodes upward until their parents match. This gives the lowest common ancestor in O(log n) time.

For each query, the code reconstructs the frequency counts along the path using prefix subtraction. The most common edge weight is preserved, while every other edge must be modified.

Go Solution

package main

import (
	"math"
)

func minOperationsQueries(n int, edges [][]int, queries [][]int) []int {
	graph := make([][][2]int, n)

	for _, edge := range edges {
		u, v, w := edge[0], edge[1], edge[2]

		graph[u] = append(graph[u], [2]int{v, w})
		graph[v] = append(graph[v], [2]int{u, w})
	}

	log := int(math.Ceil(math.Log2(float64(n)))) + 1

	parent := make([][]int, log)

	for i := range parent {
		parent[i] = make([]int, n)

		for j := range parent[i] {
			parent[i][j] = -1
		}
	}

	depth := make([]int, n)

	freq := make([][]int, n)

	for i := range freq {
		freq[i] = make([]int, 27)
	}

	var dfs func(node, par int)

	dfs = func(node, par int) {
		parent[0][node] = par

		for _, next := range graph[node] {
			nei := next[0]
			weight := next[1]

			if nei == par {
				continue
			}

			depth[nei] = depth[node] + 1

			copy(freq[nei], freq[node])

			freq[nei][weight]++

			dfs(nei, node)
		}
	}

	dfs(0, -1)

	for k := 1; k < log; k++ {
		for node := 0; node < n; node++ {
			prev := parent[k-1][node]

			if prev != -1 {
				parent[k][node] = parent[k-1][prev]
			}
		}
	}

	lca := func(u, v int) int {
		if depth[u] < depth[v] {
			u, v = v, u
		}

		diff := depth[u] - depth[v]

		for k := 0; k < log; k++ {
			if (diff & (1 << k)) != 0 {
				u = parent[k][u]
			}
		}

		if u == v {
			return u
		}

		for k := log - 1; k >= 0; k-- {
			if parent[k][u] != parent[k][v] {
				u = parent[k][u]
				v = parent[k][v]
			}
		}

		return parent[0][u]
	}

	answer := make([]int, 0, len(queries))

	for _, query := range queries {
		u, v := query[0], query[1]

		ancestor := lca(u, v)

		pathLength := depth[u] + depth[v] - 2*depth[ancestor]

		maxFrequency := 0

		for weight := 1; weight <= 26; weight++ {
			count := freq[u][weight] +
				freq[v][weight] -
				2*freq[ancestor][weight]

			if count > maxFrequency {
				maxFrequency = count
			}
		}

		answer = append(answer, pathLength-maxFrequency)
	}

	return answer
}

The Go implementation follows the same algorithmic structure as the Python version.

A few Go-specific details are worth noting:

• The adjacency list uses slices of fixed-size arrays [2]int
• copy() is used to duplicate frequency arrays efficiently
• Parent arrays are initialized to -1
• Closures are used for both DFS and LCA functions
• Integer overflow is not a concern because all values remain well within Go's int range

Worked Examples

Example 1

n = 7

edges:
0-1 (1)
1-2 (1)
2-3 (1)
3-4 (2)
4-5 (2)
5-6 (2)

DFS Frequency Construction

Node	Path From Root	Weight Counts
0	[]	{1:0, 2:0}
1	[1]	{1:1, 2:0}
2	[1,1]	{1:2, 2:0}
3	[1,1,1]	{1:3, 2:0}
4	[1,1,1,2]	{1:3, 2:1}
5	[1,1,1,2,2]	{1:3, 2:2}
6	[1,1,1,2,2,2]	{1:3, 2:3}

Query [0,3]

Path:

0 -> 1 -> 2 -> 3

Weights:

1,1,1

Value	Result
Path length	3
Max frequency	3
Answer	0

Query [2,6]

Path:

2 -> 3 -> 4 -> 5 -> 6

Weights:

1,2,2,2

Value	Result
Path length	4
Max frequency	3
Answer	1

Query [0,6]

Weights:

1,1,1,2,2,2

Value	Result
Path length	6
Max frequency	3
Answer	3

Complexity Analysis

Measure	Complexity	Explanation
Time	O((n log n) + (m log n))	DFS and LCA preprocessing plus logarithmic query handling
Space	O(n log n + 26n)	Ancestor table and frequency storage

The DFS traversal visits each node once. Building the binary lifting table requires O(n log n) time.

Each query performs:

• one LCA computation in O(log n)
• a scan across 26 weights, which is constant time

Therefore, total query processing is O(m log n).

The space usage comes primarily from:

• the binary lifting table
• cumulative frequency arrays

Since weights are capped at 26, the frequency storage is effectively linear.

Test Cases

from typing import List

class Solution:
    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:
        import math

        graph = [[] for _ in range(n)]

        for u, v, w in edges:
            graph[u].append((v, w))
            graph[v].append((u, w))

        log = math.ceil(math.log2(n)) + 1

        parent = [[-1] * n for _ in range(log)]
        depth = [0] * n
        freq = [[0] * 27 for _ in range(n)]

        def dfs(node: int, par: int):
            parent[0][node] = par

            for nei, weight in graph[node]:
                if nei == par:
                    continue

                depth[nei] = depth[node] + 1
                freq[nei] = freq[node][:]
                freq[nei][weight] += 1

                dfs(nei, node)

        dfs(0, -1)

        for k in range(1, log):
            for node in range(n):
                prev = parent[k - 1][node]

                if prev != -1:
                    parent[k][node] = parent[k - 1][prev]

        def lca(u: int, v: int) -> int:
            if depth[u] < depth[v]:
                u, v = v, u

            diff = depth[u] - depth[v]

            for k in range(log):
                if diff & (1 << k):
                    u = parent[k][u]

            if u == v:
                return u

            for k in range(log - 1, -1, -1):
                if parent[k][u] != parent[k][v]:
                    u = parent[k][u]
                    v = parent[k][v]

            return parent[0][u]

        answer = []

        for u, v in queries:
            ancestor = lca(u, v)

            path_length = depth[u] + depth[v] - 2 * depth[ancestor]

            max_frequency = 0

            for weight in range(1, 27):
                count = (
                    freq[u][weight]
                    + freq[v][weight]
                    - 2 * freq[ancestor][weight]
                )

                max_frequency = max(max_frequency, count)

            answer.append(path_length - max_frequency)

        return answer

sol = Solution()

# Example 1
assert sol.minOperationsQueries(
    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]]
) == [0,0,1,3]

# Example 2
assert sol.minOperationsQueries(
    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]]
) == [1,2,2,3]

# Single node path
assert sol.minOperationsQueries(
    2,
    [[0,1,5]],
    [[0,0]]
) == [0]

# All edges already equal
assert sol.minOperationsQueries(
    4,
    [[0,1,2],[1,2,2],[2,3,2]],
    [[0,3]]
) == [0]

# All edges different
assert sol.minOperationsQueries(
    4,
    [[0,1,1],[1,2,2],[2,3,3]],
    [[0,3]]
) == [2]

# Star-shaped tree
assert sol.minOperationsQueries(
    5,
    [[0,1,1],[0,2,1],[0,3,2],[0,4,2]],
    [[1,2],[1,3],[3,4]]
) == [0,1,0]

# Deep chain tree
assert sol.minOperationsQueries(
    5,
    [[0,1,1],[1,2,2],[2,3,2],[3,4,2]],
    [[0,4]]
) == [1]

# Multiple mixed queries
assert sol.minOperationsQueries(
    6,
    [[0,1,1],[1,2,1],[1,3,2],[3,4,2],[3,5,3]],
    [[2,4],[2,5],[4,5]]
) == [1,2,1]

Test Summary

Test	Why
Example 1	Verifies correctness on provided sample
Example 2	Verifies another complex sample
Single node path	Ensures zero-length paths work correctly
All edges already equal	Confirms answer becomes zero
All edges different	Tests maximum modification behavior
Star-shaped tree	Validates branching structures
Deep chain tree	Tests linked-list-like trees
Multiple mixed queries	Ensures repeated independent queries work correctly

Edge Cases

Query Between The Same Node

If a == b, the path contains no edges. A naive implementation might incorrectly attempt frequency calculations or produce negative values.

This implementation handles the case naturally because:

path_length = 0

and all frequencies become zero, so the answer is also zero.

Skewed Trees

A tree may resemble a linked list:

0 - 1 - 2 - 3 - 4

In such cases, naive DFS per query becomes very expensive because paths may contain nearly all nodes.

The preprocessing approach avoids repeated traversal by storing cumulative frequencies once during DFS.

Paths With Completely Different Weights

Consider a path like:

1,2,3,4

Every weight frequency equals one.

The implementation correctly computes:

4 - 1 = 3

meaning three edges must be changed.

Paths Where All Weights Already Match

If every edge on the path already shares the same weight, the maximum frequency equals the total number of edges.

The formula:

path_length - max_frequency

correctly returns zero without requiring any special handling.