2846. Minimum Edge Weight Equilibrium Queries in a Tree LeetCode Solution
In this guide, you will get 2846. Minimum Edge Weight Equilibrium Queries in a Tree LeetCode Solution with the best time and space complexity. The solution to Minimum Edge Weight Equilibrium Queries in a Tree problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimum Edge Weight Equilibrium Queries in a Tree
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:
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.
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
Complexity Analysis
Time Complexity: O(n\log n + q(26 + \log n))
Space Complexity: O(n\log n)
2846. Minimum Edge Weight Equilibrium Queries in a Tree LeetCode Solution in C++
class Solution {
public:
vector<int> minOperationsQueries(int n, vector<vector<int>>& edges,
vector<vector<int>>& queries) {
constexpr int kMax = 26;
const int m = log2(n) + 1;
vector<int> ans;
vector<vector<pair<int, int>>> graph(n);
// jump[i][j] := the node you reach after jumping 2^j from i
vector<vector<int>> jump(n, vector<int>(m));
// count[i][j] := the count of j from root to i, where 1 <= j <= 26
vector<vector<int>> count(n);
// depth[i] := the depth of i
vector<int> depth(n);
for (const vector<int>& edge : edges) {
const int u = edge[0];
const int v = edge[1];
const int w = edge[2];
graph[u].emplace_back(v, w);
graph[v].emplace_back(u, w);
}
count[0] = vector<int>(kMax + 1);
dfs(graph, 0, /*prev=*/-1, 0, jump, count, depth);
// Calculate binary lifting.
for (int j = 1; j < m; ++j)
for (int i = 0; i < n; ++i)
jump[i][j] = jump[jump[i][j - 1]][j - 1];
for (const vector<int>& query : queries) {
const int u = query[0];
const int v = query[1];
const int lca = getLCA(u, v, jump, depth);
// the number of edges between (u, v).
const int numEdges = depth[u] + depth[v] - 2 * depth[lca];
// the maximum frequency of edges between (u, v)
int maxFreq = 0;
for (int j = 1; j <= kMax; ++j)
maxFreq = max(maxFreq, count[u][j] + count[v][j] - 2 * count[lca][j]);
ans.push_back(numEdges - maxFreq);
}
return ans;
}
private:
void dfs(const vector<vector<pair<int, int>>>& graph, int u, int prev, int d,
vector<vector<int>>& jump, vector<vector<int>>& count,
vector<int>& depth) {
if (prev != -1)
jump[u][0] = prev;
depth[u] = d;
for (const auto& [v, w] : graph[u]) {
if (v == prev)
continue;
// Inherit the count from the parent.
count[v] = count[u];
// Add one to this edge.
++count[v][w];
dfs(graph, v, u, d + 1, jump, count, depth);
}
}
// Returns the lca(u, v) via Calculate binary lifting.
int getLCA(int u, int v, const vector<vector<int>>& jump,
const vector<int>& depth) {
// v is always deeper than u.
if (depth[u] > depth[v])
return getLCA(v, u, jump, depth);
// Jump v to the same height of u.
for (int j = 0; j < jump[0].size(); ++j)
if (depth[v] - depth[u] >> j & 1)
v = jump[v][j];
if (u == v)
return u;
// Jump u and v to the node right below the lca.
for (int j = jump[0].size() - 1; j >= 0; --j)
if (jump[u][j] != jump[v][j]) {
u = jump[u][j];
v = jump[v][j];
}
return jump[v][0];
}
}; /* code provided by PROGIEZ */
2846. Minimum Edge Weight Equilibrium Queries in a Tree LeetCode Solution in Java
class Solution {
public int[] minOperationsQueries(int n, int[][] edges, int[][] queries) {
final int kMax = 26;
final int m = (int) (Math.log(n) / Math.log(2)) + 1;
int[] ans = new int[queries.length];
List<Pair<Integer, Integer>>[] graph = new List[n];
// jump[i][j] := the node you reach after jumping 2^j from i
int[][] jump = new int[n][m];
// count[i][j] := the count of j from root to i, where 1 <= j <= 26
int[][] count = new int[n][];
// depth[i] := the depth of i
int[] depth = new int[n];
for (int i = 0; i < n; ++i)
graph[i] = new ArrayList<>();
for (int[] edge : edges) {
final int u = edge[0];
final int v = edge[1];
final int w = edge[2];
graph[u].add(new Pair<>(v, w));
graph[v].add(new Pair<>(u, w));
}
count[0] = new int[kMax + 1];
dfs(graph, 0, /*prev=*/-1, 0, jump, count, depth);
// Calculate binary lifting.
for (int j = 1; j < m; ++j)
for (int i = 0; i < n; ++i)
jump[i][j] = jump[jump[i][j - 1]][j - 1];
for (int i = 0; i < queries.length; ++i) {
final int u = queries[i][0];
final int v = queries[i][1];
final int lca = getLCA(u, v, jump, depth);
// the number of edges between (u, v).
final int numEdges = depth[u] + depth[v] - 2 * depth[lca];
// the maximum frequency of edges between (u, v)
int maxFreq = 0;
for (int j = 1; j <= kMax; ++j)
maxFreq = Math.max(maxFreq, count[u][j] + count[v][j] - 2 * count[lca][j]);
ans[i] = numEdges - maxFreq;
}
return ans;
}
private void dfs(List<Pair<Integer, Integer>>[] graph, int u, int prev, int d, int[][] jump,
int[][] count, int[] depth) {
if (prev != -1)
jump[u][0] = prev;
depth[u] = d;
for (Pair<Integer, Integer> pair : graph[u]) {
final int v = pair.getKey();
final int w = pair.getValue();
if (v == prev)
continue;
// Inherit the count from the parent.
count[v] = count[u].clone();
// Add one to this edge.
++count[v][w];
dfs(graph, v, u, d + 1, jump, count, depth);
}
}
// Returns the lca(u, v) via Calculate binary lifting.
private int getLCA(int u, int v, int[][] jump, int[] depth) {
// v is always deeper than u.
if (depth[u] > depth[v])
return getLCA(v, u, jump, depth);
// Jump v to the same height of u.
for (int j = 0; j < jump[0].length; ++j)
if ((depth[v] - depth[u] >> j & 1) == 1)
v = jump[v][j];
if (u == v)
return u;
// Jump u and v to the node right below the lca.
for (int j = jump[0].length - 1; j >= 0; --j)
if (jump[u][j] != jump[v][j]) {
u = jump[u][j];
v = jump[v][j];
}
return jump[v][0];
}
} // code provided by PROGIEZ
2846. Minimum Edge Weight Equilibrium Queries in a Tree LeetCode Solution in Python
class Solution:
def minOperationsQueries(
self,
n: int,
edges: list[list[int]],
queries: list[list[int]],
) -> list[int]:
kMax = 26
m = int(math.log2(n)) + 1
ans = []
graph = [[] for _ in range(n)]
# jump[i][j] := the node you reach after jumping 2^j from i
jump = [[0] * m for _ in range(n)]
# count[i][j] := the count of j from root to i, where 1 <= j <= 26
count = [[] for _ in range(n)]
# depth[i] := the depth of i
depth = [0] * n
for u, v, w in edges:
graph[u].append((v, w))
graph[v].append((u, w))
def dfs(u: int, prev: int, d: int):
if prev != -1:
jump[u][0] = prev
depth[u] = d
for v, w in graph[u]:
if v == prev:
continue
# Inherit the count from the parent.
count[v] = count[u][:]
# Add one to this edge.
count[v][w] += 1
dfs(v, u, d + 1)
count[0] = [0] * (kMax + 1)
dfs(0, -1, 0)
# Calculate binary lifting.
for j in range(1, m):
for i in range(n):
jump[i][j] = jump[jump[i][j - 1]][j - 1]
def getLCA(u: int, v: int) -> int:
"""Returns the lca(u, v) via Calculate binary lifting."""
# v is always deeper than u.
if depth[u] > depth[v]:
return getLCA(v, u)
# Jump v to the same height of u.
for j in range(m):
if depth[v] - depth[u] >> j & 1:
v = jump[v][j]
if u == v:
return u
# Jump u and v to the node right below the lca.
for j in range(m - 1, -1, -1):
if jump[u][j] != jump[v][j]:
u = jump[u][j]
v = jump[v][j]
return jump[v][0]
for u, v in queries:
lca = getLCA(u, v)
# the number of edges between (u, v).
numEdges = depth[u] + depth[v] - 2 * depth[lca]
# the maximum frequency of edges between (u, v)
maxFreq = max(count[u][j] + count[v][j] - 2 * count[lca][j]
for j in range(1, kMax + 1))
ans.append(numEdges - maxFreq)
return ans # code by PROGIEZ
