下面分析一下LCT的构建和应用(要用到splay,不会的建议先学splay):
首先先了解LCT的用处:支持一系列树的操作,如合并,分裂,换根,查询节点数,判断是否在一棵树里,判断深度,甚至还可以当LCA用;下面讲讲做法:
要学LCT首先要清楚几个概念:轻重边,重儿子,辅助树,以及一系列东西,,,我在文中不会用这些名词,,尽量通俗易懂的讲。
动态树(LCT)的一系列操作无非就是依赖于几个基本操作:换根(makeroot()),access(将某个节点到其根节点的路径变为重路径,或者说把这条路径用splay维护起来),splay(将某个节点转到所在splay的根),,嗯,大致就是这些。
现在讲一下这些操作的具体实现:
1、 首先是最重要的access,它几乎是所有操作的基础,它的作用是用splay将某个节点到根节点的路径维护起来。具体实现我们可以看一下代码:
void access(int o,int x=0) {
for(;o;o=fa[x=o]) splay(o),rc(o)=x;
}
其实非常短,当然是压行之后,我们来看看压行之前
void access(int o) {
int x=0;
while(o!=0) {
splay(o);
rc(o)=x;
x=o;
o=fa[o]
}
}
这几行代码就是全部操作了,我们先来看一下代码中的一些用法,在我的代码中,原树的根节点的父亲是0,所有的空儿子也是0,也就是说0代表一个空的节点,它没有实际意义,只是用来防止越界的。再来介绍一下splay的意义,splay维护的是某一条链,它以该节点在原树中的深度为关键字,也就是说某个节点的左子树中的节点都比该节点的深度下,而右子树中的所有节点都比该节点的深度大;在splay中,节点的父节点仅代表它在splay中的父节点,而splay中根的父节点是该splay中深度最小的点在原树中的父节点(也可以说是该条链的父节点);
在该函数中,fa[o]是o的父节点,while(o!=0)的意思是说o节点当前还在某棵splay中,没有到达空节点,而o一旦访问到空节点,就说明我们已经将节点到根的路径都访问完了,access也就可以结束了。splay(o)是将o节点伸展到该splay的根,这时断开o的右子树(即将原链中的比它深度大的节点扔掉)(rc(o)是o节点的右儿子),并将使x成为它的右子树,而x记得是上一棵访问的splay的根,相当于将节点o到根的路径上的每段splay都合并起来(不理解的可以画图一步一步的模拟一下)。
2、 然后是splay操作,该操作与splay树没有太大差别,但是要注意标记的下传(如下文要讲的翻转标记re[]),以前打splay时都是自顶向下寻找节点是进行标记的下传,但是LCT的所有操作都是自底向上的,所以在splay(o)时要将fa[o]与o都进行下传,如果是双旋的话,就要传三个标记,fa[fa[o]],fa[o],和o都要更新。所以splay还有一个作用就是更新标记,所以一定要在刚进入函数时就markdown一下,因为有些节点已经是splay的根节点了,但是仍旧要进行标记的下传。
还有需要注意的是rorate中要进行特判:
if(!isroot(f)) ch[fa[f]][is(f)]=o;
这句话很重要!如果节点o的父亲是该splay的根的话,那么就不能将节点o的祖父的孩子设成o,因为左右孩子记录的都是节点在splay中的信息,而显然如果o的父亲是splay的根节点,那么o的祖父与o不再一棵splay中,那么o祖父的孩子信息就不能修改。但是父亲的信息显然是可以修改的,因为旋转后o为splay的根节点,他的父节点就应该是上一棵splay,所以当然可以修改啦。
下面是代码:
void rorate(int o) {
int f=fa[o],d=is(o),c=ch[o][d^1];
if(!isroot(f)) ch[fa[f]][is(f)]=o; fa[o]=fa[f];
if(c) fa[c]=f; ch[f][d]=c;
fa[f]=o;ch[o][d^1]=f;
}
void splay(int o) {
if(o==0) return;
markdown(fa[o]);markdown(o);
while(!isroot(o)) {
markdown(fa[fa[o]]);markdown(fa[o]);markdown(o);
if(isroot(fa[o])) rorate(o);
else if(is(o)==is(fa[o])) rorate(fa[o]),rorate(o);
else rorate(o),rorate(o);
} return;
}
isroot()的作用是判断该节点是否为splay的根,is()用来判断该节点是其父亲的左孩子还是右孩子;
代码:
int is(int o) { return rc(fa[o])==o; }
int isroot(int o) { return !fa[o]||(lc(fa[o])!=o&&rc(fa[o])!=o); }
3、接下来是换根操作(makeroot(o)),该操作的作用是将节点o变成整棵树的根,所以要先进行一次access(o),将其与根节点置与一棵splay中,然后splay(o)将o转至splay的根,这时由于节点o是该条路径中的深度最深的点,那么在splay中将o转至根后该棵splay中的其他节点就都在该节点的左子树中,然后在该节点打一个翻转标记,将splay翻转,这样其他所有节点就都在o的右子树中了,这样o节点变成了该splay中深度最小的节点,当然就是根了;
代码如下:
void makeroot(int o) {
access(o);splay(o);re[o]^=1;
}
4、下面是LCT中的link和cut操作,也算是LCT的特色了;
link(u,v)操作就是将u节点与v节点相连,所以我们将u变成u所在树的根节点makeroot(u),然后将fa[u]=v即可。注意不可修改其他父子关系,,原因与上文rorate中的原因类似。
cut(u,v)是将u,v间的边断开,所以先将u变成根makeroot(u),由于u,v相连,那么此时在原树中v到根的路径必然只包含两个点u,v,所以access(v)就得到了一棵只包含u,v的splay,然后将v转至根节点splay(v),lc(v)=0,fa[u]=0即可;
代码如下:
void link(int a,int b) {
makeroot(a);fa[a]=b;
}
void cut(int a,int b) {
makeroot(a);access(b);splay(b);
lc(b)=0;fa[a]=0;
}
LCT中重要的操作就是这几个,其他的操作都可以由此变化实现,如前面提的查询节点数,在操作中维护一个变量size即可,而求LCA的操作则也可以实现,如:
LCA(u,v):
1、先access(u),splay(u),查看一下v所在splay的根是否为u,如果是的话,那么LCA(u,v)=v;
2、然后access(v),此时再splay(v),查询一下u所在splay中的根节点为是否为v,如果是的话那么LCA(u,v)=u;
3、否则的话splay(u),LCA(u,v)=fa[u];
这个结论是很显然的,如果u,v的LCA是他们中的某一个的话,那么假设LCA(u,v)=u,那么u一定在v到根节点的路径上,在第二步时,access(v)以后u就与v在一棵子树中,所以LCA(u,v)=u,所以第二个步骤成立。第一步同理。
考虑第二种情况,如果LCA(u,v)=t,那么在前两步执行完后,u在splay的根的父节点一定在v所在的splay中,且splay(u)后,fa[u]==LCA(u,v);证毕。
最后希望大家注意几个问题,有助于理解,一是LCT与其他树结构不同,是自底向上构建与更新的,码代码时要考虑周全;还有就是要分清LCT中原树的父子关系与splay中的父子关系,,在实现时的要注意关系的变换。那些概念我没有将,网上应该能查到很多,我就不赘述了。 还有就是在一开始建树时不必想链剖那样先遍历一遍,,将所有链都维护,,可以将所有的节点当作一棵独立的splay,在用到某个节点时再将节点到根的路径上的splay连起来即可。。
以上就是我要讲的全部内容了,以后可能会有补充,这是今天学完LCT后的一些理解,可能有些地方考虑不全,比如代码有bug或者时间复杂度太高之类的,,,有意见尽管评论,,我一定尽快回复。
如果想看模板的话,可以看我的另一篇博客那里面有LCT的模板,是结合题目的,,希望有所帮助。