在搞LCT之前，我們不妨再看看喜聞樂見的樹鏈剖分。

樹鏈剖分有一道喜聞樂見的例題：NOI2015 軟件包管理器

如果你看懂題目了，你就會明白它是叫你維護一個樹，這棵樹是不會動的，要茲磁子樹求和，子樹修改，樹上路徑求和，樹上路徑修改。

樹鏈剖分就是把一個樹剖分成像這樣的東西：

一棵樹用一坨重鏈組成，重鏈之間用輕鏈連接。

對于樹上的每一個點，它和子樹大小最大的那個的根節(jié)點在同一重鏈，其他兒子另成一條新重鏈。

這樣可以證明每個點到根至多只有l(wèi)og級這么多段的連續(xù)的重鏈。

然后我們把連續(xù)的一坨重鏈用線段樹維護一下。

代碼（常數(shù)非常大

#include <iostream> #include <stdio.h> #include <stdlib.h> using namespace std; #define SIZ 266666 namespace segt { #define LC(x) ((x)<<1) #define RC(x) (LC(x)+1) int M=131072,ls[SIZ],rs[SIZ],tag[SIZ],sum[SIZ]; inline bool avb(int x) {return 1<=x&&x<=2*M; } void pd(int x) {if(!avb(x)||tag[x]==-1) return;if(avb(LC(x))) tag[LC(x)]=tag[x];if(avb(RC(x))) tag[RC(x)]=tag[x];sum[x]=(rs[x]-ls[x]+1)*tag[x]; tag[x]=-1; } void upd(int x) {pd(LC(x)); pd(RC(x));sum[x]=0;if(avb(LC(x))) sum[x]+=sum[LC(x)];if(avb(RC(x))) sum[x]+=sum[RC(x)]; } int query(int cur,int l,int r) {if(!avb(cur)||l>r) return 0;pd(cur);if(ls[cur]==l&&rs[cur]==r) return sum[cur];int mid=(ls[cur]+rs[cur])>>1;int ans=query(LC(cur),l,min(mid,r))+query(RC(cur),max(mid+1,l),r);upd(cur);return ans; } void edit(int cur,int l,int r,int x) {if(!avb(cur)||l>r) return;pd(cur);if(ls[cur]==l&&rs[cur]==r) {tag[cur]=x; return;}int mid=(ls[cur]+rs[cur])>>1;edit(LC(cur),l,min(mid,r),x);edit(RC(cur),max(mid+1,l),r,x);upd(cur); } void init() {for(int i=1;i<=M;i++) sum[i+M]=0, ls[i+M]=rs[i+M]=i, tag[i+M]=-1;for(int i=M-1;i>=1;i--){tag[i]=-1; sum[i]=sum[LC(i)]+sum[RC(i)];ls[i]=ls[LC(i)]; rs[i]=rs[RC(i)];} } } namespace lct //然而只是鏈剖 { int n,S=0,ns[SIZ],fs[SIZ],ss[SIZ], fa[SIZ],siz[SIZ],ws[SIZ],dep[SIZ], fe[SIZ],top[SIZ],X=0,ls[SIZ]; void setc(int s,int f) //setchild {fa[s]=f; ++S; ns[S]=fs[f]; fs[f]=S; ss[S]=s; } void dfs1(int cur) {siz[cur]=1; ws[cur]=0;int csc=-233;for(int x=fs[cur];x;x=ns[x]){int c=ss[x];fa[c]=cur;dep[c]=dep[cur]+1;dfs1(c);if(siz[c]>csc) csc=siz[c], ws[cur]=c;siz[cur]+=siz[c];} } void dfs2(int cur,int tp) {fe[cur]=++X; top[cur]=tp;if(ws[cur]) dfs2(ws[cur],tp);for(int x=fs[cur];x;x=ns[x]){int c=ss[x];if(c!=ws[cur]) dfs2(c,c);}ls[cur]=X; } void s2(int cur) {printf("%d\n",segt::query(1,fe[cur],ls[cur]));segt::edit(1,fe[cur],ls[cur],0); } void s1(int x) {int u=1,v=x,ds=dep[v]-dep[u]+1,sum=0;int f1=top[u],f2=top[v];while(f1!=f2){if(dep[f1]<dep[f2]) swap(f1,f2), swap(u,v);//u is deeper...sum+=segt::query(1,fe[f1],fe[u]);segt::edit(1,fe[f1],fe[u],1);u=fa[f1]; f1=top[u];}if(dep[u]>dep[v]) swap(u,v);sum+=segt::query(1,fe[u],fe[v]);segt::edit(1,fe[u],fe[v],1);printf("%d\n",ds-sum); } } int main() {int n,tmp;scanf("%d",&n);for(int i=2;i<=n;i++){scanf("%d",&tmp);lct::setc(i,tmp+1);}lct::dfs1(1); lct::dfs2(1,1);segt::init();int Q;scanf("%d",&Q);char iu[20]; int x;while(Q--){scanf("%s%d",iu,&x);++x;if(iu[0]=='i') lct::s1(x);else lct::s2(x);} }

稍微做一點說明吧。

dfs1這個函數(shù)就是基本的一些處理，dfs2這個函數(shù)是用來分配輕重鏈的。

然后子樹操作就只要把這個子樹里面的所有重鏈在線段樹里面修改就行。

鏈的代碼：

void s1(int x) {int u=1,v=x,ds=dep[v]-dep[u]+1,sum=0;int f1=top[u],f2=top[v];while(f1!=f2){if(dep[f1]<dep[f2]) swap(f1,f2), swap(u,v);//u is deeper...sum+=segt::query(1,fe[f1],fe[u]);segt::edit(1,fe[f1],fe[u],1);u=fa[f1]; f1=top[u];}if(dep[u]>dep[v]) swap(u,v);sum+=segt::query(1,fe[u],fe[v]);segt::edit(1,fe[u],fe[v],1);printf("%d\n",ds-sum); }

在u和v不在同一條重鏈上時，把u和v所在重鏈頭（就是同一條重鏈上深度最小的）中深度大的那個往上走，順路更新線段樹。

當u和v在同一條重鏈上時直接修改線段樹就可以了。此時深度比較小的那個就是lca。（你想這樣求lca的話我也沒意見

那如果是不是邊權(quán)而是點權(quán)的話就把父向邊的邊權(quán)設為點權(quán)就行，路經(jīng)詢問時記得要統(tǒng)計一下lca的點權(quán)，同樣子樹詢問的時候要統(tǒng)計一下根節(jié)點的點權(quán)。

因為每個點到根的路徑上至多有l(wèi)og級的重鏈，像這樣搞的復雜度大概是O(logn*數(shù)據(jù)結(jié)構(gòu))。如果你用線段樹來維護那就是O(log^2n)。但是實際復雜度往往到不了這個級別…

LCT和鏈剖也是類似的，也是把一個樹(或森林，下文為了方便就直接說是樹了)剖成若干條鏈，但是這里的重鏈和輕鏈有區(qū)別，每訪問一個點，我們就把它到根的路徑全變成重鏈。這個訪問操作一般叫做“access”。

在LCT中我們把這個“重鏈”叫做Preferred Edge，把一段不能再延伸的重鏈叫做Preffered Path，如果結(jié)點v的子樹中，最后被訪問的結(jié)點在子樹w中，這里w是v的兒子，那么就稱w是v的Preferred Child，如果最后被訪問過的結(jié)點就是v本身，那么它沒有Preferred Child。

access操作看起來像這樣：

LCT主體用splay維護，和鏈剖一樣，splay里面的一條重鏈是存在一棵子樹里的。但是這顆splay的father比較特殊…如果一個點它是這條重鏈splay里面最上面的一個點，那么它的父親就是樹上實際的父親，否則就是正常splay的父親。

剩下的事情呢如果泥會splay就比較trivial了。你要access一個點，你就把它旋到這條重鏈的頂上，此時它的父親就是樹上的父親了對吧。然后把右子樹接到這條重鏈上面的下一個點。然后把“下一個點”設為這個點，再往父親走。

那么為什么要接右子樹呢？因為我們希望中序遍歷的時候是連續(xù)的一條重鏈…這個隨意理解一下，至于右子樹怎么辦……愛怎么辦怎么辦，因為右子樹的父親不會變啊，而且右子樹對應的也就是鏈上深度低一點的某一個點，所以并沒有什么事情。

接下來還有一個基本操作叫makeroot(x)，這個操作意思是讓x成為整棵樹的根。我們先access(x)（使x到根節(jié)點為一條重鏈），然后splay(x)（使x成為這條重鏈最上面的一個點），然后再把x這棵子樹打一個翻轉(zhuǎn)標記就行了。

為什么這樣是可行的呢？因為x這個重鏈以外的東西跟根是什么并沒有什么關(guān)系，只要把x這條重鏈翻轉(zhuǎn)過來x就會在最頂上了。

然后findroot(x)，找到x所在子樹在原樹上的根節(jié)點（因為makeroot可能會改變根節(jié)點）。這個最簡單，先access(x)，然后splay(x)，然后一直往左孩子找，找到最左邊splay一下然后返回就行。（為什么要splay回去？似乎不splay也行…復雜度玄學

然后cut(a,b)，把樹中a和b的連邊切斷，搞成兩棵新樹。先makeroot(a)，然后access(b)，然后splay(b)，最后把b的左孩子和a的父親都設為0。

還有l(wèi)ink(a,b)，把a和b中間連一條邊。先makeroot(a)，然后fa[a]不是為空嗎，就fa[a]=b，最后在splay(a) （又是玄學

這樣LCT就嘴巴寫完啦。代碼稍后放下一篇文章放

轉(zhuǎn)載于:https://www.cnblogs.com/zzqsblog/p/5438694.html

總結(jié)

以上是生活随笔為你收集整理的链剖LCT总结的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。