题目分析

该问题是在树形结构上处理动态更新与路径查询的组合问题。情报网络构成一棵有根树，需要处理两种操作：危险值的动态更新和路径信息的实时查询。

核心思路

1. 树结构建模

• 情报网络构成以大头目为根的树形结构
• 每个节点（除根节点）有且仅有一个父节点
• 树具有连通性，任意两节点间存在唯一路径

2. 危险值管理机制

• 初始阶段所有节点危险值为0
• 当节点开始搜集情报时，记录开始时间start_day
• 当前危险值计算公式：max(0, current_day - start_day - 1)
• 危险值随时间单调递增

3. 路径查询处理

对于查询(X, Y, C)：

1. 计算X和Y的最近公共祖先LCA
2. 路径总节点数 = depth[X] + depth[Y] - 2 × depth[LCA] + 1
3. 分别遍历路径X→LCA和Y→LCA，统计危险值大于C的节点数量

算法步骤

预处理阶段

1. 构建树结构并确定根节点
2. 进行DFS遍历，计算每个节点的深度
3. 预处理LCA查询所需的倍增表

查询处理阶段

对于每个任务：

• 搜集情报任务：记录该节点的开始时间，标记该节点进入危险状态
• 传递情报任务：
  • 使用LCA算法找到路径的最近公共祖先
  • 沿路径遍历所有节点，计算路径长度和威胁节点数
  • 输出路径总节点数和危险值超过C的节点数

关键性质

1. 路径唯一性：树上任意两点间存在唯一简单路径
2. 危险值单调性：一旦节点开始搜集情报，其危险值随时间单调不减
3. LCA应用：通过LCA可以高效分解任意路径为两条直上直下的路径

复杂度分析

• 预处理：DFS遍历O(n)，LCA预处理O(n log n)
• 更新操作：O(1)时间记录开始时间
• 查询操作：O(路径长度)时间遍历统计