树上启发式合并 | DSU on tree

简述

树的结构让某些数据难以直接快速合并,所以就有了树上启发式合并,一种把合并时间为\(O(n)\)优化成\(O(\log n)\)的神奇方式。如果您先前学习过树链剖分,那么学习树上启发式合并就非常简单了。

继续阅读树上启发式合并 | DSU on tree

LCT 的一类题目

LCT 简述

LCT (Link Cut Tree) 是一种维护树链的灵活的数据结构。与线段树不同的是,LCT 一般使用 Splay 这种非常优雅、灵活的数据结构来维护树链。因为 LCT 支持动态增边、删边,所以很多题目就可以打破一些限制进行求解。

继续阅读LCT 的一类题目

[Fortuna OJ]Jul 6th – Group B 解题报告

A – 调整 Tweak

这道题我在考场上打了一个错解,还骗到了 30 分。

正常的思路是:在最短路图上找到几个边进行修改。然而,最优的解决方案并不一定出现在最短路图上的边上,也可以通过修改次优边进行解决。所以,这道题其实跟最短路没什么太大关系,即使后面会用到 Djisktra 来求最短路。

我们可以把一个\(G(V, E), |V| = n, |E| = m\)复制\(n\)份,然后对于第\(k\)份图中的有向边\((u_k, v_k, w_k)\),可以生成一个副本来连接下一层的目标点,也就是每一条边会派生出\((u_k, v_{k + 1}, 0)\),当最后求最短路时,经过这样的一条边可以被认为是修改一条边,且,这个边是单向向下的,所以不会出现同一层修改多次的情况。最后只需要求这张图的最短路,然后判定满足\(dist[n_k] \leq c\)的最小\(k\)就行了。

继续阅读[Fortuna OJ]Jul 6th – Group B 解题报告

树上差分

初步认识树上差分

学习树上差分的前提是:

  • 最近公共祖先(LCA)
  • 线性差分

学习了这些之后,我们就可以开始学习树上差分了。树上差分的思想跟差分类似:都是在不得不求前缀和的情况下,将区间操作变为单点操作,降低复杂度。树上差分曾两次在 NOIp 系列比赛中出现过,所以学习树上差分很有必要(我怀疑是出题组不敢出树链剖分,但又要考察选手们对树上操作的熟悉程度,所以采用了这么个坑爹玩意)。我们先来学习一个基本的操作:点的链上区间加

继续阅读树上差分