第 154 场双周赛-20250412

https://leetcode.cn/contest/biweekly-contest-154/

中国时间：2025-04-12 22:30, 1 小时 30 分

给你一个整数 n 和一个以节点 1 为根的无向带权树，该树包含 n 个编号从 1 到 n 的节点。它由一个长度为 n - 1 的二维数组 edges 表示，其中 edges[i] = [ui, vi, wi] 表示一条从节点 ui 到 vi 的无向边，权重为 wi。

同时给你一个二维整数数组 queries，长度为 q，其中每个 queries[i] 为以下两种之一：

[1, u, v, w'] – 更新节点 u 和 v 之间边的权重为 w'，其中 (u, v) 保证是 edges 中存在的边。
[2, x] – 计算从根节点 1 到节点 x 的最短路径距离。

返回一个整数数组 answer，其中 answer[i] 是对于第 i 个 [2, x] 查询，从节点 1 到 x 的最短路径距离。

示例 1：

输入： n = 2, edges = [[1,2,7]], queries = [[2,2],[1,1,2,4],[2,2]]

输出： [7,4]

解释：

查询 [2,2]：从根节点 1 到节点 2 的最短路径为 7。
操作 [1,1,2,4]：边 (1,2) 的权重从 7 变为 4。
查询 [2,2]：从根节点 1 到节点 2 的最短路径为 4。

示例 2：

输入： n = 3, edges = [[1,2,2],[1,3,4]], queries = [[2,1],[2,3],[1,1,3,7],[2,2],[2,3]]

输出： [0,4,2,7]

解释：

查询 [2,1]：从根节点 1 到节点 1 的最短路径为 0。
查询 [2,3]：从根节点 1 到节点 3 的最短路径为 4。
操作 [1,1,3,7]：边 (1,3) 的权重从 4 改为 7。
查询 [2,2]：从根节点 1 到节点 2 的最短路径为 2。
查询 [2,3]：从根节点 1 到节点 3 的最短路径为 7。

示例 3：

输入： n = 4, edges = [[1,2,2],[2,3,1],[3,4,5]], queries = [[2,4],[2,3],[1,2,3,3],[2,2],[2,3]]

输出： [8,3,2,5]

解释：

查询 [2,4]：从根节点 1 到节点 4 的最短路径包含边 (1,2)、(2,3) 和 (3,4)，权重和为 2 + 1 + 5 = 8。
查询 [2,3]：路径为 (1,2) 和 (2,3)，权重和为 2 + 1 = 3。
操作 [1,2,3,3]：边 (2,3) 的权重从 1 变为 3。
查询 [2,2]：最短路径为 2。
查询 [2,3]：路径权重变为 2 + 3 = 5。

提示：

1 <= n <= 10^5
edges.length == n - 1
edges[i] == [ui, vi, wi]
1 <= ui, vi <= n
1 <= wi <= 10^4
输入保证 edges 构成一棵合法的树。
1 <= queries.length == q <= 10^5
```
queries[i].length == 2
```
或
```
4
```
- queries[i] == [1, u, v, w']，或者
- queries[i] == [2, x]
- 1 <= u, v, x <= n
- (u, v) 一定是 edges 中的一条边。
- 1 <= w' <= 10^4

这个题目是一棵带权树的路径查询与边权更新问题，可以通过构建树结构 + 差分或树剖/DFS序来高效处理路径查询和单边更新。

✅ 题解思路概览

树是无环连通图，每两个节点之间有唯一路径；
你需要支持修改一条边的权重；
同时支持查询从根节点 1 到某节点 x 的路径权重和；
所以这是一个典型的“边权树的路径查询 + 单边更新”问题；

✅ 解决方案

我们可以采用如下方法：

用邻接表建树结构 + DFS 预处理每个节点的路径和

用一个 tree[x] 表示以节点 x 为起点的邻接边 (v, weight)；
DFS 从根节点 1 出发，记录从根到每个节点的路径和 dist[x]；
同时记录每条边 (u, v) 的唯一 ID，建立 edge_map[(u,v)] = eid（或 edge_map[frozenset([u,v])]）用于后续快速找到边的编号；
用 edge_weights[eid] 记录当前边的权重；
当查询 [2, x] 时，直接返回 dist[x]；
当更新 [1, u, v, w] 时，找到边 (u,v) 的 ID，更新 edge_weights，并从 u 或 v 中较深的子树重新 DFS 修正 dist。

优化 DFS 更新

树是单一方向的，所以边的更新只影响某个子树。
用 DFS 记录每个节点的 parent，以及 depth；
当更新边 (u, v) 的权重时，从深的节点 child 开始更新其子树的 dist[x]。
所以我们可以维护 in[x] 和 out[x] 的 DFS 序范围（Euler Tour 技术），将 dist[x] 存入数组，借助线段树/树状数组进行区间加法。

✅ 推荐解法：Euler Tour + 树状数组（或 Segment Tree）

用 DFS 建立 Euler Tour，记录每个节点的 in_time[x]；
初始化时构建 dist[x] 数组；
构建差分数组，在 [in[x], out[x]] 之间加一个值 delta 表示其子树都受到了边权变化的影响；
所以更新操作变成区间加法，查询操作变成前缀和。

✅ Python 实现（基于树状数组 BIT）

python

from typing import List
import sys
sys.setrecursionlimit(1 << 25)

class BIT:
    def __init__(self, n):
        self.n = n + 2
        self.tree = [0] * (self.n)

    def update(self, i, x):
        while i < self.n:
            self.tree[i] += x
            i += i & -i

    def query(self, i):
        res = 0
        while i > 0:
            res += self.tree[i]
            i -= i & -i
        return res

    def range_add(self, l, r, x):
        self.update(l, x)
        self.update(r + 1, -x)

class Solution:
    def treeQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:
        from collections import defaultdict

        # 建树 + 边id映射
        tree = [[] for _ in range(n + 1)]
        edge_id = dict()
        eid = 0
        for u, v, w in edges:
            tree[u].append((v, w, eid))
            tree[v].append((u, w, eid))
            edge_id[frozenset([u, v])] = eid
            eid += 1

        # 预处理
        in_time = [0] * (n + 1)
        out_time = [0] * (n + 1)
        dist = [0] * (n + 1)
        parent = [-1] * (n + 1)
        edge_weights = [0] * (n)
        time = 1

        def dfs(u, p):
            nonlocal time
            in_time[u] = time
            time += 1
            for v, w, eid in tree[u]:
                if v == p:
                    continue
                parent[v] = u
                dist[v] = dist[u] + w
                edge_weights[eid] = w
                dfs(v, u)
            out_time[u] = time - 1

        dfs(1, -1)

        # 初始化 BIT
        bit = BIT(n + 2)
        for i in range(1, n + 1):
            bit.range_add(in_time[i], in_time[i], dist[i])

        res = []

        for q in queries:
            if q[0] == 1:
                _, u, v, new_w = q
                eid = edge_id[frozenset([u, v])]
                old_w = edge_weights[eid]
                delta = new_w - old_w
                edge_weights[eid] = new_w

                # 找出更深的 child
                if parent[u] == v:
                    child = u
                else:
                    child = v

                bit.range_add(in_time[child], out_time[child], delta)
            else:
                _, x = q
                res.append(bit.query(in_time[x]))

        return res

✅ 示例运行

python

n = 4
edges = [[1,2,2],[2,3,1],[3,4,5]]
queries = [[2,4],[2,3],[1,2,3,3],[2,2],[2,3]]
print(solve(n, edges, queries))  # 输出: [8,3,2,5]

✅ 时间复杂度分析

建树 DFS 初始化：O(n)
每次查询/更新操作：O(log n)
总体复杂度：O(n + q log n)，可通过 10^5 规模的数据。

第 154 场双周赛-20250412 ​

E3512.使数组和能被K整除的最少操作次数 ​

M3513.不同XOR三元组的数目I ​

M3514.不同XOR三元组的数目II ​

T3515.带权重树中的最短路径 ​

第 154 场双周赛-20250412

E3512.使数组和能被K整除的最少操作次数

M3513.不同XOR三元组的数目I

M3514.不同XOR三元组的数目II

T3515.带权重树中的最短路径