Minimum Edge Weight Equilibrium Queries in a Tree — LeetCode 2846 Python Solution
HardTreeGraphArrayStrongly Connected Component
- Problem
- #2846
- Pattern
- Tree Traversal
- Reading time
- 8 min
- Source
- leetcode.com
The 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.
Example
- 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.
Python solution
Python
class Solution:
def minOperationsQueries(
self, n: int, edges: List[List[int]], queries: List[List[int]]
) -> List[int]:
m = n.bit_length()
g = [[] for _ in range(n)]
f = [[0] * m for _ in range(n)]
p = [0] * n
cnt = [None] * n
depth = [0] * n
for u, v, w in edges:
g[u].append((v, w - 1))
g[v].append((u, w - 1))
cnt[0] = [0] * 26
q = deque([0])
while q:
i = q.popleft()
f[i][0] = p[i]
for j in range(1, m):
f[i][j] = f[f[i][j - 1]][j - 1]
for j, w in g[i]:
if j != p[i]:
p[j] = i
cnt[j] = cnt[i][:]
cnt[j][w] += 1
depth[j] = depth[i] + 1
q.append(j)
ans = []
for u, v in queries:
x, y = u, v
if depth[x] < depth[y]:
x, y = y, x
for j in reversed(range(m)):
if depth[x] - depth[y] >= (1 << j):
x = f[x][j]
for j in reversed(range(m)):
if f[x][j] != f[y][j]:
x, y = f[x][j], f[y][j]
if x != y:
x = p[x]
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)
return ansComplexity
| Measure | Complexity |
|---|---|
| Time | O((n + q) \times C \times \log n) |
| Space | O(n \times C \times \log n) auxiliary |
Pattern: Tree Traversal
Choose the order — preorder, inorder, postorder, level — and the problem solves itself. LeetCode 2846. Minimum Edge Weight Equilibrium Queries in a Tree is filed here because LeetCode tags it Tree, which is the vocabulary this hub collects.
The tree traversal guide has the Python template for the pattern and the 225 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 2846. Minimum Edge Weight Equilibrium Queries in a Tree?
- LeetCode 2846. Minimum Edge Weight Equilibrium Queries in a Tree is rated Hard on LeetCode.
- What is the time complexity of LeetCode 2846. Minimum Edge Weight Equilibrium Queries in a Tree?
- The Python solution on this page runs in O((n + q) \times C \times \log n).
- What is the space complexity of LeetCode 2846. Minimum Edge Weight Equilibrium Queries in a Tree?
- The Python solution on this page uses O(n \times C \times \log n) auxiliary space.
- What topics does LeetCode 2846. Minimum Edge Weight Equilibrium Queries in a Tree cover?
- LeetCode 2846. Minimum Edge Weight Equilibrium Queries in a Tree is tagged Tree, Graph, Array and Strongly Connected Component on LeetCode.