第 450 场周赛-20250518

https://leetcode.cn/contest/weekly-contest-450/

中国时间：2025-05-18 10:30, 1 小时 30 分

给你一个 无向带权 树，共有 n 个节点，编号从 0 到 n - 1。这棵树由一个二维整数数组 edges 表示，长度为 n - 1，其中 edges[i] = [ui, vi, wi] 表示存在一条连接节点 ui 和 vi 的边，权重为 wi。

此外，给你一个二维整数数组 queries，其中 queries[j] = [src1j, src2j, destj]。

返回一个长度等于 queries.length 的数组 answer，其中 answer[j] 表示一个子树的 最小总权重 ，使用该子树的边可以从 src1j 和 src2j 到达 destj 。

这里的子树是指原树中任意节点和边组成的连通子集形成的一棵有效树。

示例 1：

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

输出： [12,11]

解释：

蓝色边表示可以得到最优答案的子树之一。

answer[0]：在选出的子树中，从 src1 = 2 和 src2 = 3 到 dest = 4 的路径总权重为 3 + 5 + 4 = 12。
answer[1]：在选出的子树中，从 src1 = 0 和 src2 = 2 到 dest = 5 的路径总权重为 2 + 3 + 6 = 11。

示例 2：

输入： edges = [[1,0,8],[0,2,7]], queries = [[0,1,2]]

输出： [15]

解释：

answer[0]：选出的子树中，从 src1 = 0 和 src2 = 1 到 dest = 2 的路径总权重为 8 + 7 = 15。

提示：

3 <= n <= 10^5
edges.length == n - 1
edges[i].length == 3
0 <= ui, vi < n
1 <= wi <= 10^4
1 <= queries.length <= 10^5
queries[j].length == 3
0 <= src1j, src2j, destj < n
src1j、src2j 和 destj 互不不同。
输入数据保证 edges 表示的是一棵有效的树。

下面是一种基于「重心技巧」+「预处理 LCA 和点到根的距离」的方法，将整棵树随意以一个节点（如 0）作为根，然后用一次 DFS/并搭配倍增预处理：

预处理
- 选定一个根（比如 0），对整棵树做一次 DFS，计算出每个节点到根的距离 dist[u]（即从根走到 u 的路径权重之和），并记录深度 depth[u]，以及 up[k][u]：u 的第 $2^{k}$ 级祖先。
- 这样就可以在 $O (\log n)$ 时间内求任意两点 $u, v$ 在这棵「原始固定根」下的 LCA，以及它们之间的距离
  $dist (u, v) = dist [u] + dist [v] - 2 dist [LCA (u, v)]$ .
变根 LCA
- 对于每个查询 $(s_{1}, s_{2}, d)$ ，我们需要知道在 以 $d$ 为根 的树中， $s_{1}$ 与 $s_{2}$ 的 LCA（记作 ${LCA}_{d} (s_{1}, s_{2})$ ），才能求出它们到 $d$ 的公共路径重叠部分的长度。
- 经典技巧：在原始以 0 为根的倍增表里，令
  ${LCA}_{0} (s_{1}, s_{2}), b = {LCA}_{0} (s_{1}, d), c = {LCA}_{0} (s_{2}, d)$ .
  那么「以 $d$ 为根时」的 LCA 就是这三者中深度最大的那个节点：
  $x = \arg max_{v \in {a, b, c}} (depth [v])$ .
计算答案
- 令
  $D_{1} = dist (s_{1}, d), D_{2} = dist (s_{2}, d), D_{x} = dist (x, d) .$
- 则所求子树的最小总代价正好是
  $D_{1} + D_{2} - D_{x},$
  因为从 $s_{1}$ 和 $s_{2}$ 到 $d$ 的两条路径公共部分（即从 $x$ 到 $d$ ）只选一次。

整体时间复杂度：

预处理： $O (n \log n)$
每个查询： $O (\log n)$
共 $n, q \leq 10^{5}$ ，完全可以接受。

python

import sys
sys.setrecursionlimit(10**7)
from typing import List

class Solution:
    def minimumWeight(self, edges: List[List[int]], queries: List[List[int]]) -> List[int]:
        n = len(edges) + 1
        LOG = (n-1).bit_length()
        # 建图
        g = [[] for _ in range(n)]
        for u,v,w in edges:
            g[u].append((v,w))
            g[v].append((u,w))

        # up[k][u]: u 的第 2^k 级祖先（相对于根 0）
        up = [[-1]*n for _ in range(LOG)]
        depth = [0]*n
        dist = [0]*n      # dist[u]: 从根 0 到 u 的距离

        # DFS 预处理 depth, dist, up[0]
        def dfs(u, p):
            up[0][u] = p
            for v,w in g[u]:
                if v == p: continue
                depth[v] = depth[u] + 1
                dist[v]  = dist[u] + w
                dfs(v, u)

        dfs(0, -1)

        # 倍增表
        for k in range(1, LOG):
            for u in range(n):
                prev = up[k-1][u]
                up[k][u] = -1 if prev < 0 else up[k-1][prev]

        # 原始根 0 下的 LCA
        def lca(u: int, v: int) -> int:
            if depth[u] < depth[v]:
                u, v = v, u
            # 先把 u 提到和 v 同层
            diff = depth[u] - depth[v]
            for k in range(LOG):
                if diff >> k & 1:
                    u = up[k][u]
            if u == v:
                return u
            # 同步向上
            for k in reversed(range(LOG)):
                if up[k][u] != up[k][v]:
                    u = up[k][u]
                    v = up[k][v]
            return up[0][u]

        # 任意两点距离
        def get_dist(u: int, v: int) -> int:
            w = lca(u, v)
            return dist[u] + dist[v] - 2 * dist[w]

        ans = []
        for s1, s2, d in queries:
            # 在以 d 为根的树中，s1 与 s2 的 LCA
            a = lca(s1, s2)
            b = lca(s1, d)
            c = lca(s2, d)
            # 三者中 depth 最大者
            x = a
            if depth[b] > depth[x]:
                x = b
            if depth[c] > depth[x]:
                x = c

            D1 = get_dist(s1, d)
            D2 = get_dist(s2, d)
            Dx = get_dist(x, d)
            ans.append(D1 + D2 - Dx)

        return ans

关键点回顾：

树上两点距离可由「根到各点的预处理距离」+「普通 LCA」在 $O (1)$ 内算出。
用「三 LCA 取深度最大者」的技巧，迅速完成「树重根」后任意两点 LCA 的查询。
最终答案利用「两条路径长度之和减去公共部分」即可得到。

第 450 场周赛-20250518 ​

E3550.数位和等于下标的最小下标 ​

M3551.数位和排序需要的最小交换次数 ​

M3552.网络传送门旅游 ​

T3553.包含给定路径的最小带权子树II ​

第 450 场周赛-20250518

E3550.数位和等于下标的最小下标

M3551.数位和排序需要的最小交换次数

M3552.网络传送门旅游

T3553.包含给定路径的最小带权子树II