Brief description:

…. 给定一个 n 个结点的边权树。。和 m 个事件。。。（s, t, v） 表示从时刻 0 开始。。某蚂蚁从 s 结点出发。。以速率 v 前往 t。
… 问整个运动过程中。。发生。meet or chase 事件的次数。。
（ n <= 10^6, m <= 10^3, 数据保证所有蚂蚁的速率均不相等）

Analysis:

。个人认为是 PT07 系列里最赞的一道题。。算法框架本身并不难想。。（。。O(nlogn) 预处理在线 lca。。O(m^2) 枚举每对事件。。总时间复杂度 O(nlogn + m^2)。。。）
。。。难点是一旦细节出错。。非常不容易调试。。（。。另外注意控制常数。。。例如在线 lca 的时候求 log2(x) 如果用 math 库的话。。这里会直接 TLE 成 0 分。。。

https://gist.github.com/lychees/6499849

Posted by xiaodao
Category: Play with trees