zcmimi's blog
avatar
zcmimi
2019-11-11

静态链分治用于解决静态树上众数问题,比如Codeforces\ 600E

静态链分治是离线算法,有点像莫队,复杂度\Theta (n \log n \log n)

比如说遍历一遍子树可以得出答案,但是每棵子树都遍历的话太慢了,

我们用树剖的方式把每个节点的重儿子划分出来,

遍历这个子树的时候先遍历轻儿子,再遍历重儿子,遍历重儿子后答案不清空,我们就可以省下遍历重儿子的时间

几道练手的题:

CF 375D Tree and Queries

CF570D Tree Requests

CF208E Blood Cousins

静态链分治
comment评论
Search
search