题解：环形路径上的周期性收获问题

问题分析

本题是一个复杂的周期性收获问题：

• $N$ 个员工在周长为 $L$ 的环形湖岸上匀速移动（$1$ m/s）
• $M$ 棵苹果树分布在湖岸上，每棵树收获后 $C$ 秒会重新结果
• 员工遇到成熟苹果立即收获
• 有 $Q$ 个查询：员工 $V_k$ 在时刻 $T_k$ 内收获的苹果总数

数据范围很大：$N,M,Q \le 2\times 10^5$，$T_k \le 10^{18}$，需要高效算法。

关键观察与转化

1. 树与员工的匹配

每个苹果树被哪些员工收获？由于员工匀速顺时针移动，对于树 $j$：

• 第一个收获它的员工是它顺时针方向最近的员工
• 之后，该树每次结果后会被该员工的后继员工收获（形成一个收获链）

2. 建立依赖关系

设 $fa[i]$ 表示员工 $i$ 收获的树的下一个收获者。这形成了一个有向图：

• 每个节点最多有一条出边（每个员工有一个后继）
• 图由若干链和环组成（基环内向树）

3. 时间计算

员工 $i$ 从自己的初始位置到收获第一棵树的时间是固定的。之后，从收获一棵树到收获下一棵树的时间也是固定的（取决于树的位置和重新结果时间 $C$）。

算法框架

第一步：预处理依赖关系

1. 对每个苹果树，找到顺时针方向最近的员工 $i$
2. 计算员工 $i$ 收获该树的时间
3. 建立员工之间的收获依赖关系 $fa[i]$

第二步：处理基环内向树

对于每个连通分量：

• 识别环和树部分
• 环上员工构成周期性收获序列
• 树上员工最终会"汇入"环

第三步：回答查询

对于查询 $(V_k, T_k)$：

1. 计算员工 $V_k$ 在时间 $T_k$ 内的收获数
2. 这包括：
   • 员工 $V_k$ 自己直接收获的苹果
   • 员工 $V_k$ 的后继员工收获的苹果（间接贡献）

使用树上差分 + 周期性处理：

• 树部分：使用 DFS 序 + 树状数组
• 环部分：处理模周期 $L$ 的余数

核心数据结构与技巧

1. 邻接表存储：

   • he[u] 和 to[]：存储基环内向树的边
   • heq[u] 和 id[]：存储每个员工的查询

2. DFS 处理树部分：

   • 为树部分节点分配 DFS 序
   • 使用树状数组维护子树内的收获事件

3. 环上周期性处理：

   • 环的总周期 $L$ 是所有边权之和
   • 将时间模 $L$ 处理，结合整周期数计算总收获数

4. 时间处理技巧：

   • 将时间 $T$ 分解为 $T = pL + r$（$p$ 为整周期数，$r$ 为余数）
   • 使用二分查找统计余数范围内的收获事件

算法复杂度

• 预处理：$O((N+M)\log N)$（排序和二分查找）
• DFS 遍历：$O(N)$
• 查询处理：$O((N+Q)\log N)$
• 总复杂度：$O((N+M+Q)\log N)$

对于 $N,M,Q \le 2\times 10^5$ 的数据范围完全可行。

总结

本题是一道综合性很强的基环树 + 周期性查询问题，主要考察：

1. 模型构建能力：将环形收获问题转化为基环内向图
2. 周期处理技巧：处理 $10^{18}$ 级别的时间查询
3. 数据结构综合运用：树状数组、DFS 序、邻接表
4. 分治思想：将问题分解为树部分和环部分分别处理

算法的核心在于：

• 建立员工之间的收获依赖关系，形成基环内向树
• 对树部分使用 DFS 序和树状数组高效查询
• 对环部分利用周期性，通过模运算简化计算

这种"基环树分解 + 周期性处理"的方法是解决大规模环形动态问题的有效范式，在竞赛中具有重要参考价值。