Minimum Edge Weight Equilibrium Queries in a Tree

Minimum Edge Weight Equilibrium Queries in a Tree - 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.

Input & Output

Example 1 — Basic Tree Query

$ Input: n = 4, edges = [[0,1,1],[1,2,3],[2,3,1]], queries = [[0,3]]

› Output: [1]

💡 Note: Path from 0 to 3 is: 0→1→2→3 with weights [1,3,1]. Weight 1 appears twice, weight 3 appears once. Keep weight 1, change weight 3. Answer: 3-2 = 1 operation.

Example 2 — Multiple Queries

$ Input: n = 5, edges = [[0,1,1],[1,2,1],[2,3,2],[3,4,2]], queries = [[0,4],[1,3]]

› Output: [2,1]

💡 Note: Query [0,4]: Path weights [1,1,2,2]. Weights 1 and 2 each appear twice, keep either, change 2 others. Query [1,3]: Path weights [1,2]. Different weights, change 1 of them.

Example 3 — Same Node Query

$ Input: n = 3, edges = [[0,1,5],[1,2,3]], queries = [[1,1]]

› Output: [0]

💡 Note: Query from node 1 to itself has empty path, so 0 operations needed.

Constraints

1 ≤ n ≤ 10⁴
edges.length == n - 1
edges[i].length == 3
0 ≤ u_i, v_i ≤ n - 1
1 ≤ w_i ≤ 26
1 ≤ queries.length ≤ 2 × 10⁴
0 ≤ a_i, b_i ≤ n - 1

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Tree with weighted edges and query nodes

Find Path

Use DFS to find unique path between query nodes

Count & Optimize

Count weight frequencies, keep most common

Key Takeaway

🎯 Key Insight: In a tree, there's exactly one path between any two nodes - find it, count weight frequencies, and keep the most common weight unchanged.

Asked in

G Google 25 a Amazon 18 M Microsoft 15

The key insight is to find the path between two nodes in a tree and count edge weight frequencies. The minimum operations needed equals total edges minus the most frequent weight count. Best approach uses DFS path finding with frequency counting. Time: O(m × n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Path Finding	O(m × n)	O(n)	For each query, find the path using DFS and count different edge weights
DFS with Path Reconstruction	O(m × n)	O(n)	Optimize path finding using parent tracking and early termination

Brute Force Path Finding — Algorithm Steps

Build adjacency list from edges
For each query, use DFS to find path
Count frequency of weights on path
Return path_length - max_frequency

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Graph

Create adjacency list from edges

Find Path

Use DFS to find path between query nodes

Count Weights

Count frequency of weights, keep most common

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_N 1000
#define MAX_EDGES 1000

typedef struct {
    int node;
    int weight;
} Edge;

typedef struct {
    Edge edges[MAX_N];
    int count;
} AdjList;

AdjList graph[MAX_N];
int pathWeights[MAX_N];
int pathLen;

int findPath(int start, int end, int parent) {
    if (start == end) {
        pathLen = 0;
        return 1;
    }
    
    for (int i = 0; i < graph[start].count; i++) {
        Edge edge = graph[start].edges[i];
        if (edge.node != parent) {
            if (findPath(edge.node, end, start)) {
                pathWeights[pathLen++] = edge.weight;
                return 1;
            }
        }
    }
    return 0;
}

int* solution(int n, int edges[][3], int edgesSize, int queries[][2], int queriesSize, int* returnSize) {
    *returnSize = queriesSize;
    int* result = (int*)malloc(queriesSize * sizeof(int));
    
    // Initialize graph
    for (int i = 0; i < n; i++) {
        graph[i].count = 0;
    }
    
    // Build adjacency list
    for (int i = 0; i < edgesSize; i++) {
        int u = edges[i][0], v = edges[i][1], w = edges[i][2];
        graph[u].edges[graph[u].count++] = (Edge){v, w};
        graph[v].edges[graph[v].count++] = (Edge){u, w};
    }
    
    for (int i = 0; i < queriesSize; i++) {
        int a = queries[i][0], b = queries[i][1];
        
        if (findPath(a, b, -1)) {
            if (pathLen == 0) {
                result[i] = 0;
            } else {
                // Count frequencies
                int freq[1001] = {0};  // Assuming weights are small
                int maxFreq = 0;
                
                for (int j = 0; j < pathLen; j++) {
                    freq[pathWeights[j] + 500]++;  // Offset for negative weights
                    if (freq[pathWeights[j] + 500] > maxFreq) {
                        maxFreq = freq[pathWeights[j] + 500];
                    }
                }
                
                result[i] = pathLen - maxFreq;
            }
        } else {
            result[i] = 0;
        }
    }
    
    return result;
}

int main() {
    // Simplified implementation for demo
    // In real version would need full JSON parsing
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m × n)

For each of m queries, we perform DFS which can visit up to n nodes in worst case

✓ Linear Growth

Space Complexity

O(n)

Adjacency list storage and DFS recursion stack depth

⚡ Linearithmic Space

8.8K Views

Medium Frequency

~25 min Avg. Time

342 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Path Finding — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler