LGP1600 天天爱跑步 笔记

原题链接：传送门

题意简述

给定一棵 \(N\) 个结点的树。有 \(M\) 个玩家从第 \(0\) 时刻开始从 \(s_i\) 出发，以每秒一条边的速度沿着树上的简单路径向 \(t_i\) 跑去。对于每个结点 \(j\) 都有一个观察员，会选择在 \(w_j\) 时刻观察其结点上所有玩家。问每个观察员分别能观察到多少玩家。

\(N,M\le 3\times 10^5\)。

解决方案

最暴力的做法是模拟每个玩家的跑步过程，这么做在数据随机的情况下是 \(O(MlogN)\) 的，但是会被链数据卡到 \(O(NM)\)。虽然我们可以用重链剖分把每个玩家的路径变为 \(O(NlogN)\) 级的，但是通过转化统计贡献的视角，我们可以做到严格 \(O(N)\)。