某岛

… : "…アッカリ~ン . .. . " .. .
September 10, 2013

SPOJ 1486. The Ants in a Tree

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