某島

… : "…アッカリ~ン . .. . " .. .
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