一直觉得自己写作水平比较烂，而且现在也比较懒，大家凑活着看吧

前置知识：Top Tree相关理论

什么是Weight Balanced Top Tree？

就是满足重量平衡性质的Top Tree。

重量平衡的原始定义是，对于任意节点 $u$，其任意孩子节点 $v$，满足 $v$ 的子树大小 $size(v)$ 与 $u$ 的子树大小 $size(u)$ 的比值在常数范围内。

由于严格的重量平衡性质比较难以满足，这里将条件稍微放宽为，每个Top Tree中的节点向上走 $O(1)$ 后，所在节点的子树大小能翻常数倍。后面在一些问题上可以看到这个性质的用处。

静态树上的做法

可以发现流行的全局平衡二叉树就满足重量平衡的性质。

动态树上的做法：期望复杂度

每个点赋个随机权值，一个点的重儿子是子树max最大的那个儿子。

然后再对重链建treap，轻儿子也要用treap按乱序维护。

实链上的分裂合并就是treap的分裂合并，偏好儿子的切换就按子树max的来维护。

link/cut时需要一些额外讨论。

可以证明每个点期望深度为 $O(\log{n})$。

严格来说treap实现的版本不能算重量平衡树，但是在后续一些场景的分析中，表现跟严格复杂度的版本差不多。

一份参考实现

动态树上的做法：严格复杂度

子问题：带权重量平衡树

使用平衡树维护带权序列，支持两种操作：

• merge(L,x,R)，x是单点。

• split(A,k)，表示将树A从位置k处分开。返回三元组(L,x,R)，x是单点，L,R是相应前后缀组成的平衡树。

希望的复杂度：$O(\log\frac{|L|+w(x)+|R|}{w(x)})$ 复杂度维护平衡树的结构，其中 $w(x)$ 是节点 $x$ 的权重，$|L|,|R|$ 是 $L,R$ 的子树大小

维护不变量：

一个大小k的叶子必须在第i层，满足 $2^i<=k<2^{i+2}$。

任意一个第i层的块都要满足size严格小于 $2^{i+2}$。

第i层维护的块序列中，非叶的部分可以由第 $i-1$ 层中连续几个块（可以是一个）合并得到。第i层维护的块中，相邻两个块不能都小于 $2^i$。

可以验证，全树是重量平衡的（每个点往上走 $O(1)$ 步后size就会翻至少 $O(1)$ 倍），进而有两个推论：1.全树深度为 $O(\log{n})$; 2. x的深度为 $O(\log{\frac{n}{w(x)}})$

记一个块的秩为其所在的层，注意一个块所在的层是一个连续区间（因为允许父节点只有一个孩子，可以压起来），所以其秩也是一个连续区间，实现中可以仅存储其左右端点，而无需对每一层新建一个仅有一个儿子的节点。

shrink

传入参数为两个栈和一个中间元素，$st1,st2,a$

两个栈的栈中元素均满足秩从栈顶往下单调递增，并且 $a$ 的秩不超过两个栈的栈顶元素

可以想象a是秩的最低谷，两个栈是从谷底往两侧延伸的山丘，然后我们要从a开始一点一点把中间的坑填平，将栈中节点与 $a$ 一起合并为一棵合法的树。左右两侧的栈中元素需要满足一定的性质来保证能填平。

首先将 $a$ 的秩区间 $[r1,r2]$ 变成 $[r1,r1]$，避免 $a$ 的秩虚高

每次对于谷底所在的层i，要把连续的若干个秩为i的元素合并成秩为i+1的元素，执行如下贪心策略：

• 如果 $\frac{元素size和}{2^i}<8$，直接合并
• 如果按中位线分开可以分成2半且保证size不超限，按中位线均匀分
• 则先从左到右和从右到左各贪心地切尽量长的一刀，中间剩下的部分再直接贪心切

expand

传入一个栈s，栈中元素均为树中节点。返回另一个栈s'，为将s的栈顶元素u弹掉后再将u的所有儿子按顺序加入栈

merge

将L入栈s。不断对执行 $s \leftarrow expand(s)$，直到s栈顶元素变成叶子或者栈顶元素的秩小于等于 $a$ 的秩。

对R同样操作，然后调用shrink。

split

先将树split成一个单点和两条链。直接将链入栈不可取，需要仿照merge中过程将链中元素给适当展开。

然后将左链和右链的链底的子树截下来，再调用shrink即可。

正确性

shrink过程中唯一可能违反性质的就是，某一轮填平谷底后新元素的size太小，并且此时栈顶元素（也就是未来第i层中的左右邻居）size也太小。

如果此时谷底元素已经有栈中元素参与合成了，由于栈中元素的size原本是满足条件的（是从合法的树中截出来的链），所以此时谷底元素的size一定也合法。

否则如果谷底元素size仍不合法，则在调用shrink前的过程中，栈顶元素一定会被不断expand直到合法。

完整版

用带权重量平衡树作为实链的数据结构，链剖策略使用严格重剖。注意轻子树也使用WCWBT来维护最重的儿子。

access

将一个点到根的链强制变为实链

drop

将实链上的轻边都抖落下去

注意access和drop为都需要注意轻重边切换的顺序，反了的话复杂度是错的；可以使用一个vector存储要切换的边最后再按正确顺序处理。

link/cut时需要一些额外讨论，细节这里略。

最后单次动态树操作的复杂度为严格 $O(\log{n})$，树结构上的静态查询跟普通Top Tree一样做即可。

一份参考代码实现

WBTT能干什么

首先普通Top Tree能干的WBTT基本都能干

其次是一些特殊性质的问题

树分块类的问题

问题形式大概类似于 CTS2022 WBTT

用WBTT维护树结构，对于size小于 $B$ 的子树用 $O(size)$ 的代价维护信息；查询时递归到查询区间中所有size不超过 $B$ 的子树上即可。

重量平衡的性质保证了修改的复杂度，也保证了查询时只会递归到 $O(\frac{n}{B}+\log{n})$ 个子树上，单次复杂度 $O(\sqrt{n})$

以及实际上我们还可以比这题中做得更强，由于Top Tree还给出了块间分治结构，我们在上面跑fractional cascading的话，就可以单次 $O(\sqrt{n})$ 的复杂度解决区间rank上树的问题。

关于treap版本的复杂度分析，

一个引理是，如果树的大小<=B，则从单点 $i$ 往上合并信息的期望代价 $O(B)$。考虑 $j\gt i$ 对 $i$ 的贡献，期望是 $j$ 这个后缀出现的单调栈长度，等于 $H_{n-i+1}-H_{j-i+1}$，其中 $H_i$ 表示调和级数第 $i$项。对求和式稍微放缩一下，可以得到这是 $O(树的大小)$。

完整的分析细节比较冗长，这里略。

小修改动态树上的情形

大概类似于 wcriq 上树的版本，每次修改操作是从树中间裂出一个节点，要求保证单次最坏复杂度并且维护信息。

把wcriq里的做法改改也能上树，细节略。

在洛谷博客的同步

wiki链接

双极定向是说，给定一张无向图，要求给每一条边确定一个方向，使得原无向图成为一个DAG，并且恰有一个入度为0的点 $S$ 和一个出度为0的点 $T$。wiki中似乎将这样的 $S$/$T$ 称呼为 source/sink。

显然不是所有图都有合法的双极定向。

例题——CC CUREK

原题链接

题目大意

给你一张 $n$ 个点 $m$ 条边的无向连通图，保证不存在重边和自环。

这张图的每个点都是白色的，你想要把它们全都染成黑色。刚开始你可以选择一些点把它们染成黑色，并需要付出这些点权值之和的代价；接下来你每次可以选择一个和黑点相邻的白点，并把它染成黑色。你还需要保证在每一步操作（包括最开始染那些点）之后，所有白点的导出子图连通。

请你最小化你所需要付出的代价，并构造一组代价最小时的方案。

做法

算法1

考虑树上怎么做。

首先，最多只能剩一个叶子在最开始没选，否则在染到另一个叶子的父亲时白点会不连通。

我们把点权最大的那个叶子提根，剩下每个叶子都必须在最开始被选。构方案只需要不断剥叶子即可，可以保证始终连通。

算法2

我们从树上的做法得到启发，猜想对原图建出点双树后，只有一个叶子点双最开始没有被选，同时这个叶子是所有叶子中最小权值最大的。

引理1

对于一组初始黑点的方案，满足所有白点初始均连通。则该初始方案合法，当且仅当所有白点构成的点双树上，至多只有一个叶子点双，使得其中的白点不与任何黑点相连通。

引理的必要性是显然的，跟树的情况类似证明即可。对于充分性，我们尝试对白点数量归纳并构造证明。

跟树的情况一样，我们仍然将不与所有黑点相邻的叶子点双提根，之后不断剥剩下的叶子。这样我们唯一需要实现的问题是，在一个点双内给定最开始被染黑的点（只有一个）、需要在最后一个才被染黑的点，求一组合法方案使得它满足题目中所描述的条件。

对于这个问题，每一步如果某个点染黑之后白点仍然连通，这一步就选择染黑该点。证明是简单的，我们考虑新黑点所属的点双，在该点染黑后，原点双分裂成的子点双一定摆成一条链。于是唯一可能新产生的叶子点双，必为链的两端，与新黑点相邻。这样就递归到了白点更少的子问题。

从而引理得证。

直接模拟上述做法，对于每一轮，我们跑出白点导出子图中所有的割点，那么割点就是不能剥的，非割点就是能剥的。复杂度 $O(n^2)$。

算法3

尝试直接优化算法2，发现我们实际上要操作的是删边维护割点。使用维护动态图双连通性的相关算法即可。

复杂度 $o(n^2)$。

算法4

根据前述分析，我们只需考虑原图是点双连通分量的情况，不过这时相对于原问题，会要求染黑的第一个点 $S$ 和最后一个点 $T$ 均固定。

我们尝试递归求解这个问题，但在这之前我们先思考一下有哪些递归手段。

记原图为 $G$。

• 如果 $G'$ 为 $G$ 删掉一条边得到的图，则 $G'$ 的合法删点顺序对 $G$ 也是合法的。

• 对于一个二度点 $x$，记其邻居为 $y,z$。对于任意 $G'$ 的合法删点序列 $a$，由对称性不妨设 $y$ 在 $a$中比 $z$ 更靠前，则我们在 $a$ 中 $y$ 的位置后面插入 $x$，即可将 $a$ 改进为图 $G$ 的解。

实际上只靠删边和缩二度点这两种递归手段，足以处理任意点双连通图。

具体的，我们先找出整张图的一棵生成树，然后对于每个叶子，我们保留它最浅的一条返祖边，注意这不改变点双连通性。

这样，每个叶子就都变成了二度点，我们就可以删除所有叶子啦！

如此不断操作下去，整张图就可以变为一条以 $S$ 和 $T$ 为两端点的链。此时合法删点序列的求解是平凡的，还原为原图的解序列也是容易的。

最后总复杂度$O(n)$。

应该说这里的构造过程跟 Ear_decomposition 有点像。

实际上到这里我们已经将双极定向的存在条件以及线性构造方法分析清楚了。下面是一些其它相关题目。

相关题目1——CF1192F

题目链接

可以发现本题题目描述跟上一道题很像，不过细节上有些差异，诸如在两条约束中一个形式是八连通，另一个是四连通；还有多了字典序的要求。

这题和上一题有什么相关性？

先考虑从后往前逐位构造合法解，仿照上一题，我们直接猜想，每一步任选一个与无穷远处四连通的，且删掉后剩下点集仍然八连通的点，都是合法的。

实际上这个命题是对的。只是由于一些不对称性，证明的时候需要不同的处理。

首先将命题形式改造为任一八连通图点集都存在这样的点，并且有 $min(2,点集大小)$ 个合法点。之后我们对点集大小进行归纳。取所有点中最左下方点 $u$，如果这是一个割点，则去掉该点后全集恰划分为两八连通点集 $A,B$，并且 $A,B$ 一定不会出现一个把另一个包在内部的情况——因为 $u$ 向右上方至多连出去四条边。于是由归纳假设，$A \cup \{u\}$ 和 $B \cup \{u\}$ 一定分别包含一个不等于 $u$ 的合法点，且其也是原点集的合法点。对于最右上方的点 $v$ 施以同样处理。如果 $u,v$ 均非割点，则 $u,v$ 已构成两合法点。从而命题得证。

平凡讨论有点多，您也可以选择跳过或者看官方sol。

后续做法

回到原题，问题核心变为如何即时维护所有非割点集合。关于字典序的要求是简单的，只需将存储合法点的容器换成优先队列即可。

注意到八连通意义下的割点是个局部的性质(“so the information about articulation-ness of cells is local”)。

于是修改时我们只需对周围 $O(1)$ 个点，检查其各自邻居的连通情况即可

稍微提一下细节，首先八连通的对偶是四连通，然后只需考虑上下左右四个点中同属于一个连通块的白点。

可以发现最后产生影响的一定是白点对（而不是三元组）。

然后只需考虑被检查的点删除后，配合枚举的白点对，能否产生一组割即可。您可以自行手画一下来加以理解。

具体实现的时候，需要维护两个白点是否属于同一个白四连通块。

最开始先跑一遍floodfill标记每个白点所属连通块的颜色，需要手动添加一些辅助白点。

由于修改操作只有黑变白，所以每次从新增的白点开始，暴力标记新产生的与无穷远处连通的白点即可。

相关题目2——IOI2019景点划分

题目链接

首先令 $a \le b \le c$，我们只需求出两连通点集 $A,B$ 使得 $|A|=a,|B|=b$。

考虑对原图建立圆方树，圆点表示割点，方点代表点双。圆点的权重设为1，方点的权重设为点双中的非割点数量。

显然至多只有一个点双 $C$，满足 $A \cap C$ 与 $B \cap C$ 均不为空，否则连接两点双的路径上的割点会导出矛盾。

我们枚举这个点双 $C$ 在圆方树上的方点 $u$。

将 $u$ 提根，如果 $u$ 最大的一个子树大于 $n-a$ 了，则从 $C$ 必然无法导出合法解。

否则，如果 $u$ 最大的子树大于等于 $b$，则在该子树内部任选 $b$ 个点，外部任选 $a$ 个，即得合法解。

最后一种情况，我们需要将点双 $C$ 进行拆分。考虑利用CUREK一题中的构造，我们可以得到 $C$ 中点的一个排列 $p$，使得其所有前缀与所有后缀均构成连通点集。

设 $C$ 中一个割点的权为其在圆方树上的子树大小（以 $u$ 为根），一个非割点的权为1。我们截取 $p$ 的第一个权和不小于 $a$ 的前缀，则该前缀的权和一定不超过 $a+b$——因为最大子树不超过 $b$。于是对应后缀的权和一定不小于 $b$，否则 $a+b+b \gt n$ 矛盾了。可以发现这样的前后缀切分方案导出了一组合法的原图点集划分方案。

并且这样枚举 $C$ 显然是充要的，最后总复杂度为 $O(n)$。

这是一份参考代码，一些实现细节和文中叙述有差异。

感觉在有CUREK一题作为模板的情况下思维量比官方做法小好多，不过得现写CUREK的话就有点大力飞砖了，这玩意还是有点难写的。

这里介绍一个相对通用的办法。

使用重量平衡树（能够保证每个点子树size与自身size只比严格介于 $(c,1-c)$之间的平衡树，$c$ 为取定的常数 ）维护序列非0位置。

操作2,3和操作1的区间定位没有影响。

操作1递归访问到的总节点数也不变，唯一问题是信息合并的复杂度。而这满足递归式 $T(n)=T(c*n)+T((1-c)*n)+\log{n}=O(区间长度)$。注意及时清除区间中的0元素。

于是总复杂度仍为 $O(n\log{U}+q\log^2{n})$。

并且我们现在能支持更多操作，比如单点修改权重，对复杂度的影响只有操作1中访问的节点数，均摊代价 $O(\log{U})$；比如序列分裂合并，单次代价与区间定位相同为 $O(\log^2{n})$。

关于重量平衡树，一个OI可写的实现是一种称为 WBLT 的东西。

我发现对于一些数据,很多ac程序的输出是不等的.

http://uoj.ac/submission/382182

http://uoj.ac/submission/382183

这两份提交都AC了，但按照题意显然至少有一个是错的。

这份提交 WA在extra test9了。

但是我能构造一组得到85的方案：

{20,18,15,8,8,8} $\rightarrow$ {22,22,22,22,22,22} $\rightarrow$ {22,22,22,0,0,0} $\rightarrow$ {31,30,30,30,0,0} $\rightarrow$ {30,0,0,0,0,0} $\rightarrow$ {85,0,0,0,0,0}

当我去找当时的hack记录的时候，它显示"expected: '87'"，然后我手玩了很久也没玩出来。

直到我偶然点进原始提交记录的时候，突然发现原始提交是AC的。。。

所以到底发生了什么呢？

感觉也不是很难，不过先前没听人提过。

显然题意可以转化为给定二维平面上的若干个点和若干个矩形，然后需要按某个特定的顺序取出矩形中的所有点。

一个简单的做法是对 $x$ 这一维建线段树，对线段树的每个节点维护一个set，每次需要取出点的时候就在set里通过lower_bound逐个找到需要的点。

这样复杂度是 $O(n\log^2n)$ 。

更优秀的做法是把所有点的 $y$ 坐标和询问矩形的下边界排个序，从小到大进行扫描线，同时维护出每个矩形在线段树的每个节点上lower_bound的结果。

取出点的时候，在线段树的每个节点上我们需要执行的操作是1.找到某个位置往后第一个没被删除的点;2.删除某个点。

显然这可以使用并查集做到线性，链接在这里。

代码在这里

为了方便实现以及实践效率，该代码中并没有使用线性并查集。

由于数据太水，运行时间被kdtree吊打。

反正数据结构的技能点不是技能点，打表的技能点才是技能点，随便出个T1数据乱造就好了对吧。

题目链接

很久以前我想过这个问题，但当时没有什么好的办法。

昨天去做了下江苏省选二轮的题，发现居然被出出来了。

看到问题后一个自然的想法是求出每个前缀的lyndon word分解（模板题在此）。

但是博主只知道Duval算法（可以看鏼爷论文），然后该算法需要在字符串结尾补$ - \infty $字符，如果要求出每个前缀的lyndon word分解，原来的均摊分析就失效了。

回忆一下Duval算法的过程，前缀$i$做完之后是（若干已经做好的）+（某个串s）重复t遍+s的某个前缀u。

可以证明，已经做好的部分对答案没有影响，（某个串s）重复t遍对答案有影响的部分只有第一次出现的位置，而$u$整个串都可能对答案有影响。

怎么办？

一个想法是，那就同时维护出串$u$，在执行Duval算法后的状态。

但是串$u$执行完Duval算法后会得到一个串u'，我们需要递归执行前述的过程。

容易发现$|u| \le |s| \le \frac{i}{2}$，所以这个“递归”只会有 $logn$ 层。

具体实现可以参考这份代码

让我们思考一些可能的优化。

首先一个想法是，在Duval算法运行过程中，既然串$u$在之前已经出现过了，那么是不是可以复用之前的运算结果？

记串u第一次出现的位置的结尾处为$x$

也就是说，我们猜想$ans_i=min（串s第一次出现的位置的开头，ans_x）$，注意这里的$ans_i$可以认为是$i$-题目要求输出的真实的答案。

如果这样不对，那么必然存在两个位置$p$和$q$使得前缀$x$从$p$开始和从$q$开始的循环移位都是相等的。

否则这两个位置开始的循环移位在$x$之前已经比出大小，从$x$扩展到$i$不会对大小比较产生影响。

从而前缀$x$构成的串存在非平凡整循环节$y$。

同理可以证明$y$也存在非平凡整循环节.

如此递归下去，可以得到串$x$字符全部相等，此时我们可以平凡地验证结论的正确性。

有了这个结论，配合线性SA和$O(n)-O(1)$RMQ，我们可以获得本题的一个线性算法。

不过线性SA和$O(n)-O(1)$RMQ太难写了，博主写不动。

由于lyndon word的性质和Duval算法的正确性，在处理前缀$i$的答案时，$ans_x$所对应的后缀必然大于等于串s的等长前缀。

所以我们只需使用字符串哈希判定子串相等，之后便转化为了一个子串和原串比较大小，这可以通过exkmp来线性实现。

最后提交在这里，好像比$O(nlogn)$还慢。

如果本文论述出现了漏洞，欢迎读者指出。

PS: 听说16年有篇论文提出了关于子串最小循环的$O(n)-O(1)$算法，感觉本文可能只在OI中有用。

下午上台发言的时候有点呆滞，感觉讲的东西自己都听不懂。可能讲课水平不太行。

首先考虑计数所有子串均大于等于s的串的个数。

然后对串s建立KMP自动机，补齐26n条转移边的那种。

注意根据题意，部分跳回根的转移边是不合法的

之后枚举在自动机里走了无穷多个串s之后到达的节点是点u。

由这个定义，在自动机里，从点u出发行走完一个完整的串s之后，会回到点u自己。

于是我们只要解决在一张有向图上，一个点出发走m步回到自己的方案数即可。单次复杂度$O(m * n * 26)$

由于还要枚举点u，所以总的复杂度是$O(n^2m * 26)$

而且可以发现这个算法并不依赖于n与m的大小关系。

这样我们就能获得60分啦。

实际上这个算法是有漏洞的。

一个点每条转移边并不是都能走。

想像一下，串s形如abdabc，我们现在在长度为5的前缀对应的节点上。

如果下一个字符是c，那么在这个无穷循环串中，我们就会获得一个子串abc，显然由此可以导出一个比s小的子串。

所以，每个点上所有不是跳回根的转移边只有字符最大的一条有用。

如果从根出发只走这样的转移边，那么会形成一个rho的形状。

考虑在这个rho上计数。

我们先算出$f_{i,j}$表示从根出发走i步，走到节点j的方案数。这一部分复杂度$O(nm)$。

然后还是跟之前一样枚举节点u。

如果u不经过根，那么路径唯一，方案数可以$O(1)$计算。

如果u经过根，那么枚举从u出发走几步才跳回根。这一部分复杂度也是$O(nm)$。

最后该算法总复杂度为$O(mn)$。

感觉rho的结构挺简洁的吧，不过考场上由于某些原因，并没有考虑过改进复杂度。

有没有老哥来把前面这个算法优化一下啊？

upd:

可能是可以优化的。

设生成函数F满足$f_i$为从根出发走$i$步第一次走回根的方案数。

F是可以直接在KMP过程中计算的。

所有节点走$m$步并且经过根的总方案数应该是$[x^m] (F' * x -F +1) * \frac{1}{1-F}$

复杂度应该是$O(n+mlogm)$。

大概有两种，第一种是魔改原官方题解做法，第二种则是直接避免（求出每个点的子树答案）。

算法一

2019.6.1upd:他假了，原因可以见lca的回复

在长链剖分的时候我们需要维护一个类似与滑动窗口的东西。

每次从滑动窗口里踢掉一个东西的时候，我们需要求出这个元素的真实值，官方题解在这里需要求逆。

但实际上每次遇到这种情况暴力$O(L)$地下传标记复杂度是对的。

证明的大概思路是，这样做的复杂度是链长+$\sum 每相邻两次的重叠长度$，然后对于每次重叠，一定存在一个短子树的深度大于等于重叠长度。

所以复杂度与长链剖分相同，仍为$O(n)$

算法二

一个自然的想法是通过树分治来规避求逆元。

但是一个很大的问题在于，我们仍然需要求出子连通块中的某个点到分治中心的答案，而且这一步相对于原问题没有任何简化。

我们能不能简化这一步呢？

注意到如果连通块直径不超过$L$，那么这一步是可以简单树上DP来完成的。

这就启示我们使用Top cluster 剖分。

我们可以将原树分割成$O(\frac{n}{L})$个直径不超过$L$的簇。

对于每个簇，可以预处理出，在簇的内部，两个端点的DP数组。

簇与簇之间的影响需要$O(\frac{n}{L})$次合并DP数组来计算。

合并两个DP数组的复杂度为$O(L)$，最后总复杂度为$O(\frac{n}{L} * L)=O(n)$

但是好像想要出个不能求逆的加强版比较困难，博主一时没想到有什么，不可逆，性质恰到好处，在本题中还能方便维护的信息。

算法一没有实现过，但应该是对的（吧）。

算法二的实现在这里->链接

由于滥用vector导致常数巨大，而且博主懒得卡常，所以只有80分。