洛谷1600 天天爱跑步 (树上差分)

转换思路，枚举每个观察员，统计有哪些运动员会给观察员做贡献。因为给观察员做贡献的运动员都在观察员的子树内，所以 \(dfs\) 统计即可。对于一条运动员路径，可以拆成从出发结点 \(u\) 到 \(lca\) 的路径和从 \(lca\) 的终点 \(v\) 的路径。

其中处在上行路径上的观察员 \(P\)，如果能观察到这个运动员，那么要满足

\[dep[P]+w[P] = dep[u] \]

下行路径上观察员要观察到该运动员要满足

\[w[P]-dep[P]=dis(u,v)-dep[v] \]

开一个桶，每个观察员分别对应一个桶中元素。在 \(dfs\) 枚举观察员时，同时统计当前节点作为运动员会对哪些观察员产生贡献，在桶中对应元素加上即可。统计完当前观察员，还要减去多余的贡献。