浅谈 Top Tree

浅谈 $\rm Top\ Tree$ ---- 标签：$\rm Top\ Tree$，维护子树动态树。 如果需要原始资料的话可以直接 QQ，基本上下文都是跑外网论文啃的。 ### 零. 前言 本文将介绍三种能够支持 $\rm LCT$ 原有操作，与子树修改的动态树 ~~(树分块出门左拐)~~，重于介绍基础模板的实现，理解的难度由浅入深。三份代码细节都较多，代码实现难度可看个人。 ~~（我觉得 $\rm SATT$ 最好写)~~ 1. $\rm Top\ Tree$ 是一种树的收缩合并过程形成的树。 2. 动态树有时专指 $\rm LCT$，但本文中全部代表一类支持维护一颗动态形态的树的数据结构。 3. 不建议拿这个数据结构来出题。 4. 如果看到错误的话可以评论一下，如果您因为文章的错误挂了分的话可以来私信喷我，~~评论区面子受不住~~。 5. 如果你是想学习这个数据结构，那么欢迎你往下看。如果你是被谋道毒瘤卡住，可以先看看[这个](https://www.luogu.com.cn/blog/user27338/qian-tan-zhong-gong-ye-dong-tai-shu-di-dai-ti-fang-an)，看完还是只有下数据结构能解决我们一起去喷出题人。 ### 一. 引入 LCT 对链修改能十分容易的实现，维护虚儿子套路也屡见不鲜，子树信息查询也成为了经典问题。 问题引入：[link](https://www.luogu.com.cn/problem/P5649) ### 二. 初步探索 - 从 $\rm LCT$ 开始的思考。 - 因为问题有关于动态树，我们从 $\rm LCT$ 出发，考虑优化或者魔改当前数据结构，使她能够支持新操作。 - 考虑子树修改操作。 - 我们首先得确定一个点的子树，这是容易的，对当前的根 $\rm makeroot$ ，然后 $\rm access$ 我们需要的查询点，这时查询点的所有虚儿子及其子树就是原树上他对应的子树点集。 - 那么我们现在的问题就成功转化了。即对于每个点，我们需要一个操作，能够将特定的标记下放至所有虚儿子。 - 我们定义一条树链的链头表示链上深度最浅的点。 - 首先就是一个十分 naive 的想法：用一个 $\rm set$ 暴力存下每个树点 $\rm x$ 的虚儿子所在实链的链头 $\rm y$，显然 $\rm y$ 与 $\rm x$ 在原树中一定由一条边直接相连。 - 每次暴力遍历 $\rm set$ 对所有虚儿子标记下放。  - 下图是上图的一个 $\rm LCT$ 辅助树的形态。  - 比如上图，我们对 $5$ 标记下方时就会遍历所有儿子，但是注意，当 $\rm access(2)$ 以后，我们 $1$ 的虚儿子 $\rm set$ 中存储的是 $3$ 而不是 $3$ 所在的实链的根。 - 虽然这个算法很脆弱，能被菊花图一下卡掉，但我们可以考虑优化来加强她。 ### 三. 动态开点线段树。 - 我们考虑上面那个算法的瓶颈，在于对虚儿子标记下放时耗费了太多时间，实际上我们每次变换最多只会涉及一个虚儿子，但我们将所有虚儿子的标记下放了。 - 为了快速的对虚儿子标记下放，我们希望构造的结构中每个虚儿子只有不超过 $2$ 个点和外部的点邻接。 - 我们可以较为容易的想到用一颗二叉树的结构来代替虚儿子。 - 对于每个虚儿子，我们在他的父节点开动态开点线段树，里面存储虚儿子的链头。这样我们就可以在严格 $\mathcal O(\log n)$ 的时间复杂度以内，完成对一个虚儿子的标记下放。 - 实现细节：分清楚当前点 $\rm x$，虚儿子链头 $\rm z$ 和标记下放的目标点 y 的关系。$\rm x$ 为原来 $\rm LCT\ access$ 函数中的点，$\rm y$ 为我们即将将它插到 $\rm x$ 的右儿子的点。$\rm z$ 为当前 $\rm y$ 的 $\rm splay$ 子树中的最左端点。其中 $\rm z$ 可以直接维护。 - 比如下图，$\rm id$ 表示线段树节点，若有对应实点对应的链头，因为修改是整颗 $\rm spaly$ 修改，所以 $1$ 标记下放是 $5$，但我们在 $\rm access$ 时我们要知道这个点插入父亲时它的所属链，所以记录的必须是链头。  - 时间复杂度 $\mathcal O(n\log^{2}n)$，空间复杂度 $\mathcal O(n\log n)$ 要吸氧才能过刚刚那道题。 ``` void ins_son(int &x,int y,data d,int L=1,int R=n) { if(!y)return; if(!x)x=new_node(); if(L==R)return v[x].root=y,v[x].tsum=v[x].sum=d,void(); int mid=(L+R)>>1; push_down(x); if(y<=mid)ins_son(v[x].ch[0],y,d,L,mid); if(mid<y)ins_son(v[x].ch[1],y,d,mid+1,R); push_up(x); } void del_son(int &x,int y,int p,int L=1,int R=n) { if(!y)return; if(L==R)return tag_tree(p,v[x].ttag,1),v[x]=node(1),x=0,void(); int mid=(L+R)>>1; push_down(x); if(y<=mid)del_son(v[x].ch[0],y,p,L,mid); if(mid<y)del_son(v[x].ch[1],y,p,mid+1,R); push_up(x); if(!v[x].ch[0]&&!v[x].ch[1])S[++S[0]]=x,v[x]=node(1),x=0; } int access(int x) { int ret=0; for(int y=0; x; y=x,x=v[x].fa) { splay(x); if(y)del_son(v[x].root,v[y].pre,y); if(v[x].ch[1])ins_son(v[x].root,v[v[x].ch[1]].pre,v[v[x].ch[1]].sum); v[x].ch[1]=y,push_up(x),ret=x; } return ret; } ``` ### 四.平衡树 - 我们发现上面那个算法中，做到了对标记下放的严格限制，但也导致了许多无用点的诞生，即使一个点只有一个虚儿子，我们仍会耗费 $\log$ 级别的复杂度去处理。 - 我们考虑物尽其用，即每一个虚儿子严格对应一个新建节点。这样新建节点一定不会超过 $\rm n$ 个，故总点数仍为 $\mathcal O(n)$。 - 考虑虚点的加入与删除，在 $\rm access$ 和 $\rm link$ 的时候直接操作即可。 - 那么这就是 $\rm AAA\ Tree$ 了，用平衡树维护每个节点的虚儿子，并同时上传子树信息。 - **注意这里的平衡树用单旋。**  - 再讲一下标记的下放：黑边表示允许链标记和子树标记通过，且链标记会对目标点生效。蓝边表示只允许子树标记通过，且不对目标点生效。紫边表示只允许子树标记通过，且对目标点生效，且对目标点的链标记复制子树标记。 ``` void add_son(int x,int t,int y) { v[x].ch[t]=y; v[y].fa=x; } int pos(int x) { for(int i=0; i<4; i++)if(v[v[x].fa].ch[i]==x)return i; return 4; } void ins_son(int x,int y) { if(!y)return; push_down(x); for(int i=2; i<4; i++) { if(!v[x].ch[i]) { add_son(x,i,y); return; } } while(v[x].ch[2]&&v[v[x].ch[2]].in)x=child(x,2); int z=new_node(); add_son(z,2,v[x].ch[2]); add_son(z,3,y); add_son(x,2,z); splay(z,2); } void del_son(int x) { if(!x)return; splay(x); if(!v[x].fa)return; int p=v[x].fa; if(v[p].in) { int g=v[p].fa; pre_push_down(p,2); if(g) { add_son(g,pos(p),child(p,pos(x)^1)); splay(g,2); } S[++S[0]]=p; } else { v[p].ch[pos(x)]=0; splay(p); } v[x].fa=0; } int get_fa(int x) { splay(x); if(!v[x].fa)return 0; if(!v[v[x].fa].in)return v[x].fa; int t=v[x].fa; splay(t,2); return v[t].fa; } int access(int x) { int ret=0; for(int y=0; x; y=x,x=get_fa(x)) { splay(x); del_son(y); ins_son(x,v[x].ch[1]); add_son(x,1,y); push_up(x); ret=x; } return ret; } ``` ### 五. $\rm Self - Adjusting\ Top\ Trees$ - 尽管我们解决了这样的问题，但我们的算法仍然可以继续优化。 - 一些概念 一个树簇 $\rm (cluster)$ 是树上的一个连通子图，有至多两个点和全树的其他位置连接。 这两个结点被称做界点 $\rm (boundary\ node)$。 不是界点的点被称做内点 $\rm (internal\ node)$。 这两个界点之间的路径被称做簇路径 $\rm (cluster\ path)$。  > 没有进行合并时，所有簇都是表示一个边，表示原树的一个边的簇称为 $\rm base\ cluster$。 > 我们可以把这两种操作看作合并两个簇，显然这两个簇合并之后还是簇。合并后，簇中可能和外部邻接的点是图上新边的端点，所以可以认为这个簇表示新边，表示的边的端点也就是簇的端点。显然，这样就可以一直合并到只剩一个簇。 > 我们可以对树进行若干轮收缩，每轮收缩执行 $\rm rake$ 和 $\rm compress$ 的一个极大独立操作集合，这样 $\mathcal O(\log n)$ 轮收缩后，树就只剩一条边了。最后这条边对应的簇称为根簇 $\rm (root cluster)$。 > 收缩过程中，簇的合并结构形成了一个树，我们把这个树称为 $\rm Top\ Tree$。  - 我们考虑我们想要得到的结构：  - 其中大写字母为子树点集合，由一个点与外部邻接，内部的结构与当前相似，由一条簇路径和子树构成。 - 为了得到这样的结构，我们可以先将子树内处理好，再 $\rm rake$ 到簇路径上，最后对簇路径 $\rm compress$。 - 举一个例子。  - 其中左侧为原树，右侧的边对应动态树上的虚实儿子的对应关系。  - 但在真正实现的时候，我们并不维护边信息。 - 我们发现，$\rm compress\ tree$ 和维护与标记下传跟 $\rm LCT$ 完全一样。并且 $\rm rake\ tree$ 上的相邻节点也是可旋的，即交换两次相邻的 $\rm rake$ 顺序，仍然合法。 - 我们考虑维护两颗独立的 $\rm splay$ 森林，其中 $\rm compress\ tree$ 信息就对应为原节点，$\rm rake\ tree$ 均为新增节点。 - 考虑将刚刚那张图用 $\rm splay$ 表示。  - 我们显然就可以对信息进行迅速的维护。 - 由于我们的儿子是无序的，所以 $\rm compress\ tree$ 上可以将两个 $\rm rake\ tree$ 节点压到一起，改为三叉。为实现方便，$\rm rake\ tree$ 也可以只记录一个 $\rm compress\ tree$ 节点，压为三叉。 - 操作实现： 那么我们就从简单的操作讲起，在只涉及 $\rm splay$ 形态改变的操作 $\rm rotate$，  可以发现不管怎样，在父子关系上，代表子树的节点永远不会改变，可以直接像 LCT 那样实现，但是有可能父亲相对爷爷是代表子树节点特判一下即可。 ``` if(g)v[g].ch[v[g].ch[2]==p?2:(v[g].ch[1]==p)]=x; ``` 然后就是 $\rm LCT$ 的核心操作 $\rm access$。在 tarjan 的论文中引入名为 $\rm splice$ 的操作，表示将一个簇插入到他的父亲簇上。  可以发现，原来的 $A$ 变成了 $(A+chain_x+B)$，原来的 $(B+chain_y+C)$ 变成了 $C$。  这样就完成了簇与簇之间的插入。但是在 $\rm access(x)$ 的时候，有可能 x 并不是当前簇上的末尾端点。 我们就先对 $\rm x$ 进行一次 $\rm local\ splay$ 然后把 $\rm x$ 的右儿子暴力插入到 $\rm x$ 的子树节点当中。剩下的簇与簇插入就交给 $\rm splice$ 实现即可。 $\rm Link，Cut，makeroot$ 在实现上来说与 $\rm LCT$ 十分相似。$\rm expose(x,y)$ 操作就是 $\rm makeroot(x)$ 后 $\rm access(y)$ 提出链 x-y 就可以维护，而 $\rm y$ 的子树节点对应的就是 $\rm y$ 对于 $\rm x$ 为根的子树(不包括 $\rm y$)。 虽然在手动模拟算法时 $\rm AAAT$ 与 $\rm SATT$ 的操作相似，但是由于理论基础和操作细节的处理完全不一样，故常数应分开讨论。 ### 六.$\rm Contraction-based\ Top\ Tree$ - 关于称呼：好像又叫 $\rm Worst\ Case\ Top\ Tree$，错了回来打我。 - 考虑上述 $\rm SATT$ 的一个局限性类似于 $\rm LCT$，虚儿子转移边基于势能均摊。 - 总体来说，$\rm WCTT$ 的操作类似于 $\rm SATT$，但多出来了很多精细实现。 - 考虑一个收缩方案对应的 $\rm Top\ Tree$，我们每次选择一个操作集合，对操作集合内的簇进行收缩，对一个集合操作一次叫一轮收缩，那么 $\rm Top\ Tree$ 的深度就是收缩的轮数。 - 考虑如果我们每次选择最大的操作集合，那么会有什么样的美妙性质： - 至少 $\frac{1}{2}$ 的点度数只有 $1$ 或者 $2$。显然。 - 至少 $\frac{1}{3}$ 的点会被操作。一个 $\rm RC$ 操作只影响两个簇。 - 至少减少 $\frac{1}{6}$。由上显然。 - 则一颗静态 $\rm Top\ Tree$ 的深度是 $\log$ 级别的。 - 考虑如何进行快速的 $\rm expose(u,v)$： - 暂时删除 $\rm u,v$ 作为内点 $\rm (internal\ node)$ 的所有簇。显然每层收缩中最多两个节点，则剩余森林中最多 $\log n$ 级别个剩下的连通块。 - 在其上面建立临时的 $\rm Top\ Tree$。 - 回复全局 $\rm Top\ Tree$。 - 考虑如何进行快速的维护结构： - 在 $\rm link$ 和 $\rm cut$ 以后，尽量减少原始收缩方案的该变量。 - 自下而上，首先保留原来尽可能多的收缩操作（此操作需要快速维护），再考虑加入尽可能多的新操作。考虑总共的变化量（这个是常数）。 - 那么工作原理差不多就是这样，考虑 $\rm WCTT$ 的局限性。 - 每一层需要一个 $\rm ETT$ 维护有/没有被选中的节点。 - 未匹配的节点会占用空间继续上传。 - 在实现当中，和论文上的效率差不多。 - 动态树 $\rm link - cut$ 中有比较显然的顺序 $\rm WCTT > SATT > ETT > LCT$。 - 其中在仅维护链信息的静态树情况下 $\rm WCTT$ 反超 $\rm SATT$。 - ~~应该在我的 OI 生涯中是不会再出现这个东西了吧。~~ ### 七. $\rm Euler\ Tour\ Tree$ - 不会的可以参考笔者的博客。(那一篇博客了看一看操作怎么做就好了，实现是用的正反弧，与本篇所讲的完全不同) - 我们回顾 $\rm LCT$，她的本质就是将实链用 $\rm splay$ 卷起来，缺点就在于她仅仅以深度为键值进行维护，不像括号序和欧拉环游序那样能够用一段区间表示子树。 - 考虑仅用 $\rm LCT$ 维护树的形态，树的具体信息放在另外一个数据结构上进行维护，两个数据结构之间要互相形成映射。 - 考虑 $\rm ETT$。我们称一个节点在欧拉环游序中第一次出现的地方成为代表节点，其中只有代表节点有信息，其余节点在 $\rm ETT$ 上仅作围护结构与信息传递的作用。(在算法的实现中，我们可以将这些非代表节点省略掉) - 每次 $\rm LCT$ 中 $\rm access$ 时，将 $\rm y$ 插入到 $\rm x$ 的右儿子，我们就在 $\rm ETT$ 上对应将 $\rm y$ 及她的子树区间平移到 $\rm x$ 的代表节点右边，与其相邻。 - $\rm link\ cut$ 时候在 $\rm ETT$ 上遵循欧拉序的法则即可。 - 这样做有的性质：每次 $\rm access(x)$ 后，$\rm ETT$ 上对应的前面连续一段的节点就是这条链上所有的代表节点。而 $\rm ETT$ 上每个代表节点往后数二倍子树大小个点就是包含了所有子树内节点的代表节点的子树区间。子树大小可用 $\rm LCT$ 动态维护。 - 紫色下划线代表他是代表节点，就可以维护信息了。  - 最麻烦的是换根，$\rm access$ 新根后对于前面实链上对应 $\rm ETT$ 区间翻转，同时翻转 $\rm ETT$ 的另一半区间。这样虽然保证了刚刚的性质，但是非旧根到新根之间的节点代表节点成为了最后一个，也就是反过来了。 - 我们考虑维护一个标记，表示的代表节点在最前面还是最后面，区间平移的时候就判一下父子的位置是否统一，不统一就转一下即可。 ## 后记 具体的实现细节可以去扒作者的代码，在轻重链剖分均有提交 ~~(至于哪个对应哪一个就自己找一找)~~ 。 ~~作者的好朋友应该是他自己。~~ 本来是想投 $OI-wiki$ 的，但写完了又感觉完全配不上。于是就放在这里了。 最后求个赞（ upd：代码长度过于恐怖，四篇一起放这里顺序一一对应 [code](https://www.luogu.com.cn/paste/eq274hy0) upd：ETT 常数大是因为作者实现的时候没有省略非代表节点。 upd：还是看不懂可以加Q来问我。我可以从 LCT 只查询子树信息讲起。 upd： LCT - ETT 证明了是 $O(n\log ^{2} n)$ upd：AAAT 作者自己读了读，像shik一样，所以换上 @linfourxu 的代码（ upd：LCT - ETT 证明的是作者自己的实现，某WC Au+省队julao认为可以优化到 $O(n\log n)$。（假了）