以下是 LeetCode 3515. 带权树中的最短路径 的完整 Python3 实现。核心思路与 Java/Rust 版本完全一致1. DFS 欧拉序将每个节点的子树映射到连续区间 [tin, tout]2. 懒标记线段树区间修改子树整体加 delta 单点查询节点到根距离3. 边权更新通过 parent 数组确定子节点仅更新子树区间完整 Python3 代码pythonfrom typing import Listfrom collections import defaultdictclass LazySegmentTree:Lazy Segment Tree supporting range add and point query.def __init__(self, n: int):self.n nself.tree [0] * (4 * n)self.lazy [0] * (4 * n)def _push(self, id: int, lo: int, hi: int) - None:Push lazy value down to children.if self.lazy[id] 0:returnself.tree[id] self.lazy[id]if lo ! hi:self.lazy[id * 2] self.lazy[id]self.lazy[id * 2 1] self.lazy[id]self.lazy[id] 0def add_range(self, l: int, r: int, val: int) - None:Add val to every element in range [l, r] (inclusive).self._add_range(1, 0, self.n - 1, l, r, val)def _add_range(self, id: int, lo: int, hi: int, l: int, r: int, val: int) - None:self._push(id, lo, hi)if r lo or l hi:returnif l lo and hi r:self.lazy[id] valself._push(id, lo, hi)returnmid (lo hi) // 2self._add_range(id * 2, lo, mid, l, r, val)self._add_range(id * 2 1, mid 1, hi, l, r, val)def query(self, i: int) - int:Query value at index i.return self._query(1, 0, self.n - 1, i)def _query(self, id: int, lo: int, hi: int, i: int) - int:self._push(id, lo, hi)if lo hi:return self.tree[id]mid (lo hi) // 2if i mid:return self._query(id * 2, lo, mid, i)return self._query(id * 2 1, mid 1, hi, i)class Solution:def treeQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) - List[int]:# Build adjacency listgraph [[] for _ in range(n 1)]edge_weight {}for u, v, w in edges:graph[u].append((v, w))graph[v].append((u, w))edge_weight[(min(u, v), max(u, v))] w# Euler tour arraystin [0] * (n 1)tout [0] * (n 1)parent [0] * (n 1)dist [0] * (n 1)# DFS to compute Euler tour, parent, and initial distancestime [0]def dfs(u: int, prev: int) - None:tin[u] time[0]time[0] 1for v, w in graph[u]:if v prev:continuedist[v] dist[u] wparent[v] udfs(v, u)tout[u] time[0] - 1dfs(1, 0)# Build segment tree with initial distancesseg LazySegmentTree(n)for i in range(1, n 1):seg.add_range(tin[i], tin[i], dist[i])# Process queriesans []for q in queries:if q[0] 2:# Query: shortest path from root to node xx q[1]ans.append(seg.query(tin[x]))else:# Update: change edge (u, v) weight to new_wu, v, new_w q[1], q[2], q[3]key (min(u, v), max(u, v))old_w edge_weight[key]delta new_w - old_wedge_weight[key] new_w# Determine which node is the child (deeper in the tree)child v if parent[v] u else u# Update all nodes in childs subtreeseg.add_range(tin[child], tout[child], delta)return ansPython3 特有注意点要点 说明嵌套函数 DFS 使用闭包捕获外部变量time, tin, tout 等无需手动传参线段树实现 用下划线前缀命名私有方法_push, _add_range, _query边权存储 dict 存储无向边键为有序元组 (min(u, v), max(u, v))可变整数 time 用单元素列表 [0] 实现闭包内可变引用复杂度- 时间复杂度O((n q) log n)- 空间复杂度O(n)下载文件[LeetCode3515_ShortestPathInWeightedTree.py](sandbox:///mnt/agents/output/LeetCode3515_ShortestPathInWeightedTree.py)