[洛谷P3384]【模板】树链剖分

复习板子.

树链剖分可以把树上问题转化为连续线性区间上的问题, 便于使用线段树等区间问题的工具来处理, 也可以把树上进行的操作的效率大大提高如求解LCA等等.

树剖的思路其实不难, 主要是代码长… 考虑如何把一棵树通过编号处理成尽量少的链, 同时保证每棵子树/每条链的编号都连续. 容易发现dfs序就满足前者, 这样就保证了每棵子树都在一个连续区间上. 再考虑一个贪心策略, 划分链的时候先尽量把子树节点多的节点(重儿子)纳入一条链, 得到一条重链, 其它轻儿子以同样的方法递归处理, 最终得到的链的总数是$latex \log n$级别的. 再加上一次区间维护/操作的复杂度为$latex \log n$, 总复杂度就是$latex O(n \log^2 n)$.

赞(0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址