Sweets 题解

算法思路

核心思想

本题需要高效处理树上的动态更新和查询问题。关键在于维护每个节点是否满足条件（销售技能等级 ≥ 坚韧度），并快速统计从根节点到任意节点的路径上满足条件的节点数量最大值。

关键观察

• 问题转化为：在树结构上，支持子树更新，并维护每个节点是否满足 累计学习等级 ≥ 坚韧度
• 当某个节点从不满足变为满足时，需要更新其所有后代的累计值
• 需要快速查询所有路径中满足条件的节点数的最大值

算法详解

1. 数据结构设计

树结构处理：

• 使用 DFS 序将树转化为线性序列
• dfn[x]: 节点 x 的 DFS 进入时间戳
• siz[x]: 以 x 为根的子树大小
• id[i]: 时间戳 i 对应的节点

线段树设计：

• tr: 维护每个节点作为路径终点时的成功市场数量
• tr2: 维护每个节点的 (累计学习等级 - 坚韧度) 值

2. 核心算法流程

初始化：

1. 读入树结构并建立邻接表
2. 进行 DFS 遍历，计算 DFS 序和子树大小
3. 构建两个线段树：
   • tr: 初始全为 0
   • tr2: 初始值为 -t[i]（因为初始学习等级为 0）

处理事件：

对于每个事件 (x, y):
1. 在 tr2 中将节点 x 的子树区间加上 y（增加学习等级）
2. 调用 find(1) 检查是否有节点从不满足变为满足
3. 输出当前全局最大值

关键函数 find(u):

• 如果 tr2[u].maxi < 0：子树中没有满足条件的节点，直接返回
• 如果到达叶子节点且满足条件：
  • 在 tr 中给该节点的整个子树区间加 1（因为该节点变为满足条件）
  • 将 tr2 中该节点的值设为极小值，避免重复处理
• 否则递归检查左右子树

3. 算法正确性分析

为什么这样设计：

1. tr2 维护差值：学习等级累计值 - 坚韧度，当这个值 ≥ 0 时节点满足条件
2. 子树更新：当节点 x 的学习等级增加时，x 的所有后代在访问路径上的累计学习等级都会增加
3. 惰性传播：线段树的惰性标记确保区间更新的效率

复杂度分析：

• DFS: O(n)
• 每次更新：O(log n) 的区间更新 + O(log n) 的 find 操作
• 总复杂度：O((n + q) log n)，对于 n, q ≤ 5×10^5 可接受

代码亮点

1. 双线段树设计：

   • tr 维护答案（路径上成功市场数）
   • tr2 维护条件判断（学习等级累计值 - 坚韧度）

2. DFS 序应用：

   • 将树结构转化为线性序列，便于线段树处理
   • 子树操作转化为区间操作

3. 自动触发机制：

   • 当节点满足条件时自动更新相关路径的答案
   • 避免显式检查所有节点

算法标签

• DFS 序 (DFS Order)
• 线段树 (Segment Tree)
• 惰性传播 (Lazy Propagation)
• 树链剖分思想 (Heavy-Light Decomposition Idea)
• 区间更新与查询 (Range Update and Query)
• 树上的动态规划 (Dynamic Programming on Trees)

总结

本题通过巧妙的双线段树设计，将树上的动态更新和路径查询问题高效解决。算法充分利用了 DFS 序将树结构线性化的特性，结合线段树的区间操作能力，在 O(log n) 时间内处理每个事件，整体复杂度 O((n + q) log n)，能够处理大规模数据。

关键创新点在于将"节点满足条件"这一事件转化为线段树上的数值变化，并通过自动触发机制维护全局答案，避免了暴力检查的低效做法。