事情酱紫的:我在补之前联测的某题,做法大概是在 T1,T2 上各自维护一条到根的路径(终点不一定编号相同),计算这两条路径在 T3 上对应点两两路径和。(T1,T2,T3 结点个数相同)
正解是直接在 T1,T2 上通过树分块来维护路径,我的做法是把 T1,T2 拍成括号序,然后跑一个类似于序列莫队的东西。后面的部分都是在 T3 上点分树算算。复杂度都是 O(nmlogn) 的。
但是事实是 std 最慢也就 2s 出头,我的 code 稳定在 8s 到 10s。
想知道为什么常数区别那么大(明明括号序版也就自带一个 2 的常数?)。