How do I solve the "Minimum Edge Weight Equilibrium Queries in a Tree" problem efficiently?

Use binary-tree traversal, precompute information about paths from the root, and apply path compression to handle each query in an optimized manner.

What is the primary strategy for solving this problem?

The primary strategy involves tree traversal, path compression, and efficiently using precomputed data to minimize the number of operations for each query.

Can I solve the problem without traversing the tree?

No, you need to traverse the tree to precompute useful information, as each query depends on the path between two nodes.

What kind of optimizations can I implement for large queries in this problem?

Focus on minimizing the operations by compressing paths and using efficient data structures to track edge weights and frequencies.

What is the time complexity of the solution for this problem?

The time complexity is O(n + m log n), where n is the number of nodes and m is the number of queries, with efficient preprocessing and query handling.

#2846

Hard

auto_awesome二分·树·traversal

LeetCode 题解工作台

边权重均等查询

现有一棵由 n 个节点组成的无向树，节点按从 0 到 n - 1 编号。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [u i , v i , w i ] 表示树中存在一条位于节点 u i 和节点 v i 之间、权重为 w i 的边。另给你一…

数组树图强连通分量

题目描述

现有一棵由 n 个节点组成的无向树，节点按从 0 到 n - 1 编号。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [u_i, v_i, w_i] 表示树中存在一条位于节点 u_i 和节点 v_i 之间、权重为 w_i 的边。

另给你一个长度为 m 的二维整数数组 queries ，其中 queries[i] = [a_i, b_i] 。对于每条查询，请你找出使从 a_i 到 b_i 路径上每条边的权重相等所需的 最小操作次数 。在一次操作中，你可以选择树上的任意一条边，并将其权重更改为任意值。

注意：

查询之间 相互独立 的，这意味着每条新的查询时，树都会回到 初始状态 。
从 a_i 到 b_i的路径是一个由不同节点组成的序列，从节点 a_i 开始，到节点 b_i 结束，且序列中相邻的两个节点在树中共享一条边。

返回一个长度为 m 的数组 answer ，其中 answer[i] 是第 i 条查询的答案。

示例 1：

输入：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]]
输出：[0,0,1,3]
解释：第 1 条查询，从节点 0 到节点 3 的路径中的所有边的权重都是 1 。因此，答案为 0 。
第 2 条查询，从节点 3 到节点 6 的路径中的所有边的权重都是 2 。因此，答案为 0 。
第 3 条查询，将边 [2,3] 的权重变更为 2 。在这次操作之后，从节点 2 到节点 6 的路径中的所有边的权重都是 2 。因此，答案为 1 。
第 4 条查询，将边 [0,1]、[1,2]、[2,3] 的权重变更为 2 。在这次操作之后，从节点 0 到节点 6 的路径中的所有边的权重都是 2 。因此，答案为 3 。
对于每条查询 queries[i] ，可以证明 answer[i] 是使从 a_i 到 b_i 的路径中的所有边的权重相等的最小操作次数。

示例 2：

输入：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]]
输出：[1,2,2,3]
解释：第 1 条查询，将边 [1,3] 的权重变更为 6 。在这次操作之后，从节点 4 到节点 6 的路径中的所有边的权重都是 6 。因此，答案为 1 。
第 2 条查询，将边 [0,3]、[3,1] 的权重变更为 6 。在这次操作之后，从节点 0 到节点 4 的路径中的所有边的权重都是 6 。因此，答案为 2 。
第 3 条查询，将边 [1,3]、[5,2] 的权重变更为 6 。在这次操作之后，从节点 6 到节点 5 的路径中的所有边的权重都是 6 。因此，答案为 2 。
第 4 条查询，将边 [0,7]、[0,3]、[1,3] 的权重变更为 6 。在这次操作之后，从节点 7 到节点 4 的路径中的所有边的权重都是 6 。因此，答案为 3 。
对于每条查询 queries[i] ，可以证明 answer[i] 是使从 a_i 到 b_i 的路径中的所有边的权重相等的最小操作次数。

提示：

1 <= n <= 10⁴
edges.length == n - 1
edges[i].length == 3
0 <= u_i, v_i < n
1 <= w_i <= 26
生成的输入满足 edges 表示一棵有效的树
1 <= queries.length == m <= 2 * 10⁴
queries[i].length == 2
0 <= a_i, b_i < n

lightbulb

解题思路

方法一：倍增法求 LCA

题目求的是任意两点的路径上，将其所有边的权重变成相同值的最小操作次数。实际上就是求这两点之间的路径长度，减去路径上出现次数最多的边的次数。

而求两点间的路径长度，可以通过倍增法求 LCA 来实现。我们记两点分别为 $u$ 和 $v$ ，最近公共祖先为 $x$ ，那么 $u$ 到 $v$ 的路径长度就是 $depth(u) + depth(v) - 2 \times depth(x)$ 。

另外，我们可以用一个数组 $cnt[n][26]$ 记录根节点到每个节点上，每个边权重出现的次数。那么 $u$ 到 $v$ 的路径上，出现次数最多的边的次数就是 $\max_{0 \leq j < 26} cnt[u][j] + cnt[v][j] - 2 \times cnt[x][j]$ 。其中 $x$ 为 $u$ 和 $v$ 的最近公共祖先。

倍增法求 LCA 的过程如下：

我们记每个节点的深度为 $depth$ ，父节点为 $p$ ，而 $f[i][j]$ 表示节点 $i$ 的第 $2^j$ 个祖先。那么，对于任意两点 $x$ 和 $y$ ，我们可以通过以下方式求出它们的最近公共祖先：

如果 $depth(x) < depth(y)$ ，那么交换 $x$ 和 $y$ ，即保证 $x$ 的深度不小于 $y$ 的深度；
接下来，我们将 $x$ 的深度不断向上提升，直到 $x$ 和 $y$ 的深度相同，此时 $x$ 和 $y$ 的深度都为 $depth(x)$ ；
然后，我们将 $x$ 和 $y$ 的深度同时向上提升，直到 $x$ 和 $y$ 的父节点相同，此时 $x$ 和 $y$ 的父节点都为 $f[x][0]$ ，即为 $x$ 和 $y$ 的最近公共祖先。

最后，节点 $u$ 到节点 $v$ 的最小操作次数就是 $depth(u) + depth(v) - 2 \times depth(x) - \max_{0 \leq j < 26} cnt[u][j] + cnt[v][j] - 2 \times cnt[x][j]$ 。

时间复杂度 $O((n + q) \times C \times \log n)$ ，空间复杂度 $O(n \times C \times \log n)$ ，其中 $C$ 为边权重的最大值。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

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 ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate should demonstrate a clear understanding of tree traversal techniques and path compression.
question_mark
Look for the ability to optimize query handling and precompute useful data during tree traversal.
question_mark
The candidate should be able to discuss the trade-offs between preprocessing and query handling in large datasets.

warning

常见陷阱

外企场景

error
Failing to optimize for large numbers of queries by neglecting path compression or efficient data handling.
error
Overcomplicating the problem by not leveraging tree properties or by using brute force for path queries.
error
Incorrectly calculating the minimum number of operations needed due to misunderstandings about the path and weight frequency tracking.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider cases with more complex tree structures, like binary search trees or trees with high depth.
arrow_right_alt
How would the approach change if the edges had weights beyond the simple range of 1-26?
arrow_right_alt
What optimizations can be made if the tree has additional constraints such as a high number of queries relative to nodes?

help

常见问题

外企场景

继续练习

#2646 最小化旅行的价格总和 #2603 收集树中金币 #2467 树上最大得分和路径