根据搜索结果我已经获取了LCP 05. 发LeetCoin的完整解题思路和Python3实现。这道题的核心是DFS序 带懒惰标记的线段树。解题思路核心思想DFS序 线段树这道题涉及三种操作1. 单点更新给某个成员发LeetCoin2. 区间更新给某个成员及其所有下属发LeetCoin3. 区间查询查询某个成员及其所有下属的LeetCoin总和由于团队管理结构是一棵树直接对子树操作效率低。关键技巧是1. DFS序时间戳通过DFS遍历为每个节点记录进入时间 left[u] 和离开时间 right[u]。这样以节点u为根的子树中的所有节点在DFS序中形成一个连续区间 [left[u], right[u]]2. 线段树将树上的子树操作转化为线段树上的区间操作使用带懒惰标记Lazy Propagation的线段树实现O(log n)的区间更新和查询复杂度分析- 时间复杂度建立DFS序 O(n)每次操作 O(log n)总复杂度 O(n Q·log n)- 空间复杂度O(n)---Python3 完整实现pythonclass Solution:MOD 10**9 7def bonus(self, n: int, leadership: list[list[int]], operations: list[list[int]]) - list[int]:# 构建邻接表graph [[] for _ in range(n 1)]for a, b in leadership:graph[a].append(b)# DFS序记录每个节点的子树区间 [left[u], right[u]]left [0] * (n 1) # 进入时间right [0] * (n 1) # 离开时间time 0def dfs(u: int):nonlocal timetime 1left[u] timefor v in graph[u]:dfs(v)right[u] time# 从根节点1开始DFSdfs(1)# 线段树使用4*n的数组size 4 * ntree [0] * size # 区间和lazy [0] * size # 懒惰标记def push_down(node: int, node_left: int, node_right: int):下推懒惰标记到子节点if lazy[node] 0 or node_left node_right:returnmid (node_left node_right) // 2left_child node * 2right_child node * 2 1# 更新左子节点left_len mid - node_left 1tree[left_child] (tree[left_child] lazy[node] * left_len) % self.MODlazy[left_child] (lazy[left_child] lazy[node]) % self.MOD# 更新右子节点right_len node_right - midtree[right_child] (tree[right_child] lazy[node] * right_len) % self.MODlazy[right_child] (lazy[right_child] lazy[node]) % self.MOD# 清除当前节点的懒惰标记lazy[node] 0def update(node: int, node_left: int, node_right: int, q_left: int, q_right: int, val: int):区间更新将[q_left, q_right]范围内的值增加valif q_left node_left and node_right q_right:# 完全覆盖tree[node] (tree[node] val * (node_right - node_left 1)) % self.MODlazy[node] (lazy[node] val) % self.MODreturnpush_down(node, node_left, node_right)mid (node_left node_right) // 2if q_left mid:update(node * 2, node_left, mid, q_left, q_right, val)if q_right mid:update(node * 2 1, mid 1, node_right, q_left, q_right, val)# 向上更新tree[node] (tree[node * 2] tree[node * 2 1]) % self.MODdef query(node: int, node_left: int, node_right: int, q_left: int, q_right: int) - int:区间查询查询[q_left, q_right]范围内的和if q_left node_left and node_right q_right:return tree[node]push_down(node, node_left, node_right)mid (node_left node_right) // 2res 0if q_left mid:res (res query(node * 2, node_left, mid, q_left, q_right)) % self.MODif q_right mid:res (res query(node * 2 1, mid 1, node_right, q_left, q_right)) % self.MODreturn res# 处理操作ans []for op in operations:if op[0] 1:# 单点更新给成员op[1]发op[2]个LeetCoinu op[1]update(1, 1, n, left[u], left[u], op[2])elif op[0] 2:# 区间更新给成员op[1]及其所有下属发op[2]个LeetCoinu op[1]update(1, 1, n, left[u], right[u], op[2])else:# 区间查询查询成员op[1]及其所有下属的LeetCoin总和u op[1]ans.append(query(1, 1, n, left[u], right[u]))return ans---关键要点说明要点 说明DFS序 通过一次DFS将树结构线性化使每个子树对应一个连续区间线段树数组 使用4n大小的数组存储线段树节点i的左子节点为2i右子节点为2i1懒惰标记 区间更新时先打标记查询或再次更新时才下推保证O(log n)复杂度取模 所有更新和查询结果都要对10^97取模这个实现是标准的线段树模板应用DFS序将树上的子树问题转化为区间问题线段树高效处理区间更新和查询
