题解

思路推导

把每个任务的序号看作当天的日期。若某名情报员第一次在第 $d$ 天开始搜集情报，那么在第 $t$ 天查询时，其危险值为 $t-d$。他构成威胁当且仅当 $d<t-C$，也就是 $d\le t-C-1$。

因此，每个传递任务可以改写为一个树上路径计数问题：给定阈值 $K=t-C-1$，统计路径上第一次开始搜集情报的日期不大于 $K$ 的节点数量。路径上的节点总数可以同时由树链剖分得到。

做法

先对树进行树链剖分，得到每个节点的深度、重儿子、链顶和 DFS 序。

读入全部任务。对每名情报员只记录第一次开始搜集情报的日期，并把所有传递任务按阈值 $K$ 从小到大排序。随后按日期递增地把已经满足日期不大于当前阈值的节点加入树状数组，节点的位置取其 DFS 序。

处理一个传递任务时，把 $X$ 到 $Y$ 的路径拆成若干段重链区间。每段在树状数组上查询区间和，累加后就是构成威胁的情报员数量；各段长度之和就是路径上的情报员总数。

同一名情报员再次收到搜集任务时，他已经处于持续搜集状态，因此不会改变第一次开始搜集的日期。

正确性证明

对任意在第 $t$ 天执行、风险控制值为 $C$ 的传递任务，设 $K=t-C-1$。一名已在第 $d$ 天开始搜集情报的情报员构成威胁，当且仅当 $t-d>C$，等价于 $d\le K$。按阈值处理到该任务时，树状数组中恰好包含所有且仅包含第一次搜集日期不大于 $K$ 的节点。

树链剖分把 $X$ 到 $Y$ 的唯一路径划分为若干个互不重叠的 DFS 序连续区间。因此，对这些区间的树状数组区间和求和，恰好统计路径上所有构成威胁的节点，不会遗漏或重复。区间长度求和同理恰好得到路径节点总数。故算法对每个传递任务都输出正确答案。

复杂度分析

预处理树链剖分需要 $O(n)$ 时间和 $O(n)$ 空间。每次加入节点需要 $O(\log n)$ 时间，每次路径查询被拆成 $O(\log n)$ 段，每段查询需要 $O(\log n)$ 时间，因此总时间复杂度为 $O((n+q)\log^2 n)$，空间复杂度为 $O(n+q)$。